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
versatilerk: 2016-10-22 15:36:19

any better method than prime factorisation.
got ac in 0.02 but some people have done it in 0.00

Mayank Agarwal: 2016-10-10 19:44:33

Use long long in for loop

kataria: 2016-07-22 13:47:10

easy prob.

shubiks: 2016-07-20 10:10:37

Use long long int and Fermat's!
Don't Brute force though it passes :P

square1001: 2016-07-16 12:05:59

I solved O(n^0.5 log n) for using brute force and binary search.
I got AC for 1.63 seconds, but I had to short constant-multiple speed.

divyaprakash18: 2016-07-10 08:19:11

time is sufficient.. used simple brute force to get AC ;) .....

mkfeuhrer: 2016-06-18 11:51:47

simple !! silly CE ...dnt thnk mch :-)

boney_412: 2016-06-08 20:09:21

TLE

ishrakk: 2016-06-08 07:40:47

got accepted in 0.00 sec using fermat theorerm .

Luis Herrera: 2016-05-30 04:56:56

Solved using fermat theorem.


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