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
iit2015068: 2015-10-20 21:31:29

I was trying to solve this using fermet's theorem, but got TLE.After changing my algo to brute force, solution got accepted.... So, this can be solved by brute force also.

aditya1997: 2015-10-10 08:52:18

finally ac,using wrong format specifier costed me too many TLEs.

Ravi Chandra: 2015-10-04 05:23:35

In 0.52s...Thinking hw to optimize it

Harsh Vardhan Ladha: 2015-09-02 12:20:12

unsigned long long caused me one WA

dwij28: 2015-08-30 21:45:09

I don't know why my python solution got a TLE, got an AC with almost the same code in c++ duh .. :/

rahulwahi: 2015-08-27 20:27:37

print (No) not NO
got so many wrong answer

prakash_reddy: 2015-08-14 22:12:58

Take long long in for() loop it costs me several WA.... :)

Shubhransh Srivastav: 2015-08-10 16:01:04

my 50th.... long way to go.....

Akash Goel: 2015-08-04 12:24:01

Used a naive method and got AC in 0.54.

shravinson: 2015-07-15 07:42:14

he he
finally got AC
i was printing YES for Yes


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