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
Steven: 2012-03-18 08:30:50

Sigh, why is SPOJ so slow...

Albert Chen: 2012-01-03 06:38:49

O(sqrt(n)) is no problem, but naive algorithm will fail.

Atanu: 2011-11-12 05:40:26

Please tell me if a better algo exists...I am using O(sqrt(n))

Mukul: 2011-10-19 18:07:13

ufff....TLE...:(:(

Nitin Sharma: 2011-10-01 21:03:09

Accepted when changed cin,cout to scanf and printf !!

sandeep aggrawal: 2011-07-18 19:34:06

EDIT : READ note number 1.

Last edit: 2011-08-19 14:46:36
Angel: 2011-06-24 03:13:25

I have the same problem with atanu, can u check for mine.

~: 2011-06-05 16:12:12

@atanu go for fermat's theorem..........

Atanu: 2011-06-05 10:42:27

Pawel Gawrychowski...please check!!!!!!!

Atanu: 2011-06-05 10:41:49

gives TLE...wen i run it it runs in less than half a sec.....
the judge is screwed up!!!!!!


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