HS10SQFT - Almost square factorisation

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)

Added by:Robert Gerbicz
Date:2010-11-25
Time limit:1s
Source limit:4000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GAWK ICK NODEJS SED
Resource:High School Programming League 2010/2011

hide comments
2016-04-21 14:48:14 malioboro
I have an accepted solution, but when I try with input : 403560,
it gives output: 403560=(11^2-1)*(58^2-1)=(19^2-1)*(33^2-1).
but, (19^2-1)*(33^2-1) = 391680

I think the testcase is weak, after all this years :) my solution was submitted at 2012


Last edit: 2016-04-21 14:50:09
2012-12-26 10:01:57 Ashish Lavania
30 lines of simple C++ code is more than enough
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.