TWOSQRS - Two squares or not two squares


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

hide comments
shravinson: 2015-07-15 06:51:23

i m getting WA
https://ideone.com/K8b36B

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
http://ideone.com/ihN9KU

:.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

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