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
geek_grave: 2020-12-12 11:43:51

can anyone tell me, if one didn't know Fermat's theorem, could they have come up with the solution on their own? If yes, how do you think they would have approached this?

amanjainnnn: 2020-07-31 21:02:36

Take care of output, It's "Yes" not "YES. Just wasted 3 hrs on this. Phew.
Ac Not in one Go!

mrmajumder: 2020-03-22 16:49:43

@zerodark
For test case 0, 0 = 0^2 + 0^2, because 0 is an integer.
So output will be "Yes"

zerodark: 2020-02-13 07:51:10

For Test case 0 output is NO

tarun_28: 2019-12-09 15:31:09

Explicit type conversion works well..

krish3d2y: 2019-11-20 00:24:41

AC with precomputation and binary search!! :)

killer_knight: 2019-09-29 14:18:57

make sure to use every variable as long long..costed me 1 WA :(

prashantpx_1: 2019-07-16 07:26:56

Take care of "NO" I got 1 WA for that.

sanket17: 2019-07-13 08:51:04

hint: Sometime typecating is very useful

tanav_shah1: 2019-03-26 15:40:53

Nice Problem, AC in 1 go!


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