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 eqution x^2  + y^2 + 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 seperated by single space. If no such numbers exist, then print a 0 in the line.

Input

T : number of test cases (T <= 100)
For next T lines each line contain n (n <= 10^12)

Output

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

Example

Input:
3
4
24
100
Output:
1 1
24
4 1 4 6 12
4 1 4 6 12
4 1 10 25 50

hide comments
Maroof: 2015-01-22 11:47:15

https://ideone.com/JJInts
what's wrong with my code . plz help :(

Rohan Jain: 2014-11-28 08:13:07

what shout be the output of 1 1

@Rohan Jain -> For input 1, output is 0.

Last edit: 2014-12-01 10:17:36
ivar.raknahs: 2014-09-21 15:57:43

for input=> 0
output => 0 0
finally AC ufff.

@ivar.raknahs - I don't know what your intentions are, but the above test case output you presented is WRONG ! I wasted so much time(not to mention the simplicity of the problem) and 4 WAs and kept cursing the author all because of you. Thanks !

@ Others -> for
input -> 0
output ->0

@whosoever-> but 0 0 worked for me!

Last edit: 2015-01-29 14:23:54
ABHISHEK004: 2014-06-03 10:27:17

such a waste question >:(
brute force accepted... while optimized sieve along with fermat's little theorem got TLE :(

free mind ;): 2014-03-27 17:23:43

@praveen123 : please check my solution (Runtime Error ) :(

anurag garg: 2014-01-10 20:12:34

brute force will work with optimization

Martijn Muijsers: 2013-10-30 22:16:30

YOU Sir/Madam, deserve a medal for putting this problem on here. Awesome, as a mathematician I must say this is one of the problems that I adore most.
Thanks :)

--> Thank you for appreciation :)

Last edit: 2013-12-22 17:54:02
abdelkarim: 2013-08-26 19:55:05

@praveen123 : please check my solution(WA)

numerix: 2013-08-20 12:41:47

@shivam agarwal: 154

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:0.275s-0.824s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge