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
Ankit Sultana: 2015-02-20 16:15:35

Great Question!!!

Dushyant Singh: 2015-02-16 08:59:25

After many WA's and TLE's, finally AC! :-)
TLE always makes me learn something new.

Last edit: 2015-02-16 09:11:21
utkarsha gaumat: 2015-01-23 18:54:39

im getting wa
done in root n but still

soumya poddar: 2014-12-29 08:44:29

It would be really helpful to know, if there exists any simple mathematical answer to this Question [ I am not asking for any aswer here]

Aman Agarwal: 2014-12-13 19:45:58

some tricky test case please..
because in my code the given test cases goes well but still it shows wrong answer
:(

vikax: 2014-10-27 08:59:21

@xlytron same here...

Rajat (1307086): 2014-10-25 12:44:51

Done using sieve but can be done without sieve as well........lot of Maths behind dis.

rush: 2014-10-08 15:42:20

So apparently my code is accepted when it prints "No" for 2. Weird.

Francky: 2014-10-07 18:08:12

Please consider this thread in the forum. Many thanks in advance.
Edit : no answers ...

Last edit: 2014-10-27 11:36:20
Mitch Schwartz: 2014-10-07 16:27:08

This change from Pyramid to Cube is destroying many problems. I've written to an admin about it but haven't heard back yet.

Last edit: 2014-10-07 16:27:35

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