Hardy-Ramanujan Number

Time Limit: 10 Seconds    Memory Limit: 65536 KB

According to wolfram.com:

The smallest nontrivial taxicab number, i.e., the smallest number re-presentable in two ways as a sum of two cubes. It is given by 1729 = 13 + 123 = 93 + 103.

The number derives its name from the following story G. H. Hardy told about Ramanujan. ”Once, in the taxi from London, Hardy noticed its number, 1729. He must have thought about it a little because he entered the room where Ramanujan lay in bed and, with scarcely a hello, blurted out his disappointment with it. It was, he declared, ’rather a dull number,’ adding that he hoped that wasn’t a bad omen. ’No, Hardy,’ said Ramanujan, ’it is a very interesting number. It is the smallest number expressible as the sum of two [positive] cubes in two different ways’ ” ...

Now in the ICPC (International Conference of Positive Cubes), there is a special task which nobody can do. They have a weird algorithm to generate tags and seat numbers. In order to get the algorithm to work, they need to know how many pairs of positive cube exist which their summation would be the given number N.

Can you help the ICPC team to find it out?

Input

The input contains several test cases.

In the first line of the input comes T (0 < T < 20000), the number of test cases.

Each test case is one line containing only one integer N (1 ≤ N < 264).

Output

For each test print one line containing all the pairs (pi,qi) in this format:

N=(p1^3+q1^3)=(p2^3+q2^3)=...

You can also check the sample output to see the formatting. No space characters exist in the formatting. All the pairs should be printed in the order that satisfy pi ≤ qi and p1 < p2 < p3 < ... < pK.

It is guaranteed that N could be written as the sum of two positive cubes in at least one way.

Sample Input

4
9
1729
4104
2746367559000

Sample Output

9=(1^3+2^3)
1729=(1^3+12^3)=(9^3+10^3)
4104=(2^3+16^3)=(9^3+15^3)
2746367559000=(246^3+14004^3)=(9755^3+12205^3)=(11110^3+11120^3)
Submit

Source: 13th Iran Nationwide Internet Contest - UT