For a given number n give all almost square factorisations of n, so where n = (a²-1) × (b²-1) and 1 < a ≤ b.

Input

The first line contains the number of test cases T, where T ≤ 1000. Each of the following T lines contains one integer 0 < n < 2⁶².

Output

For each test case print the case number then on a new line the factorisations in increasing order of a value. If there is no such factorisation then print an error message, see the sample input/output for the correct format!

Example

Input:
4
546939993600
100
172569415200
3467754019458593280
Output:
Case #1:
546939993600=(31^2-1)(23869^2-1)=(34^2-1)(21761^2-1)=(271^2-1)(2729^2-1)=(351^2-1)(2107^2-1)=(701^2-1)(1055^2-1)
Case #2:
For n=100 there is no almost square factorisation.
Case #3:
172569415200=(456^2-1)(911^2-1)
Case #4:
3467754019458593280=(20513^2-1)*(90781^2-1)