High School Programming League Problems Archive

For a given number n give all almost square factorisations of n,

so where n=(a^2-1)*(b^2-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^62.

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)[do not break the line here]
=(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)