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
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!

dev_gupta01: 2019-02-01 15:10:08

take care it's "No" not "NO"


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