IITKWPCF - Help Feluda with mathematical equations

no tags 

Feluda likes numbers very much but hates prime numbers too much. For a fixed n, you gave Feluda equation x2 + y2 + n = (x + y)2. Now you only want positive integral solution of x and y. Feluda being an intelligent person gave you all the pairs of (x, y) but he missed the pairs which had x as a prime number.

For all the solution that Feluda gave you, we want you to just print those values in the following format: first print the number of such x's, then the possible values x sorted in increasing order in a line separated by single space. If no such numbers exist, then print a 0 in the line.

Input

T: number of test cases (T ≤ 100). The next T lines each line contain n (n ≤ 1012)

Output

For every test case print as stated in the problem statement.

Example

Input:
3
4
24
100

Output:
1 1
4 1 4 6 12
4 1 10 25 50

hide comments
shivam agarwal: 2013-08-20 09:15:34

how many x for n=10^12??

Last edit: 2013-08-20 09:17:16

Added by:praveen123
Date:2013-08-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge