SPOJ.com - Problem IITKWPCF

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 x² + y² + n = (x + y)². 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 ≤ 10¹²)

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

Submit solution!

hide comments

< Previous 1 2 Next >

	smso: 2022-05-11 09:53:06 Take care of the case when n == 2 !
	nadstratosfer: 2018-04-09 04:23:08 For those disappointed, do it in Python - bruteforce won't work there, I tried ;) Nice problem in that its complexity rewards time spent optimizing functions for other NT problems that you can reuse here. Half year ago I would probably have TLEd with the same approach. BTW. 0 is not in the testfiles.
	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

Submit solution!

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