SPOJ.com - Problem TWOSQRS

TWOSQRS - Two squares or not two squares

#number-theory

Given integer n decide if it is possible to represent it as a sum of two squares of integers.

Input

First line of input contains one integer c <= 100 - number of test cases. Then c lines follow, each of them consisting of exactly one integer 0 <= n <= 10^12.

Output

For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible.

Example

Input:
10
1
2
7
14
49
9
17
76
2888
27

Output:
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No

Submit solution!

hide comments

< Previous 2 3 4 5 6 7 8 9 10 11 12 Next >

	shravinson: 2015-07-15 06:51:23 i m getting WA <snip> Last edit: 2022-08-18 18:05:10
	scyth3r: 2015-07-01 22:10:30 Please remember to use unsigned long long...got 9 WAs :<
	jas.py: 2015-06-26 09:53:12 i must say time limit of this question is too high which lets you solve it by brute force(which even i did 1st ;) ). But do read Two Squares Theorem and get AC in 0.01.Great Maths
	geekyadity: 2015-06-18 16:49:02 Basic Maths. However I have a slight problem. When I checked earlier that : if (isSquare(num)) { cout << "True" << endl; continue; } It gave me 3 WA's. I removed it to get an AC. But isn't any number which is a perfect square not the sum of its root and square of 0. n^(2) + (0)^(2) = n^2 <snip> Last edit: 2022-08-18 18:05:17
	:.Mohib.:: 2015-06-15 10:23:33 Nice que!! Learned a lot...!!
	Amitayush Thakur: 2015-05-28 22:41:39 Was doing a very silly error costed me 3 WAs . Be careful with overflow errors and use long long.
	kartikay singh: 2015-05-28 07:05:54 Easy ,AC in 1 go B-)
	[Mayank Pratap]: 2015-05-26 18:00:09 Enjoyed the problem .... AC 0.03 :)
	goyal: 2015-05-04 11:19:03 nice one simple math is required AC in first go
	Sue: 2015-03-08 05:40:18 10 is the number of test case :( Last edit: 2015-03-08 06:09:28

Submit solution!

Added by:	gawry
Date:	2004-06-29
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All