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
sabkx: 2021-11-04 07:16:29

0.11second O(sqrt(N)) brute force.
For the loop, use long long as well instead of int

saurabhpthk: 2021-09-11 11:03:16

one solving wd brute force, run your loop till sqrt(n)

m_coder200: 2021-02-28 18:32:36

But lengthy

m_coder200: 2021-02-28 18:32:25

It's not tough

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


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