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:
20211104 07:16:29
0.11second O(sqrt(N)) brute force.


saurabhpthk:
20210911 11:03:16
one solving wd brute force, run your loop till sqrt(n) 

m_coder200:
20210228 18:32:36
But lengthy 

m_coder200:
20210228 18:32:25
It's not tough 

geek_grave:
20201212 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:
20200731 21:02:36
Take care of output, It's "Yes" not "YES. Just wasted 3 hrs on this. Phew.


mrmajumder:
20200322 16:49:43
@zerodark


zerodark:
20200213 07:51:10
For Test case 0 output is NO 

tarun_28:
20191209 15:31:09
Explicit type conversion works well.. 

krish3d2y:
20191120 00:24:41
AC with precomputation and binary search!! :) 
Added by:  gawry 
Date:  20040629 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 