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
sea_26:
20181121 09:36:09
Accepted in one go.Using Fermat's theorem on sums of two squares.TC O(sqrt(n))


sea_26:
20181121 09:35:13
Accepted in one go.Using Fermat's theorem on sums of two squares.


tanardi gunawan:
20180906 12:35:45
if someone comment ac with brute force , that is sh1t , using fermat can ac 

prince_jain:
20180628 01:52:42
weak test cases my code gives yes to 77 instead of giving no 

nvdrag123:
20180627 12:18:34
use i<sqrt(n) instead of i * i< n in for loop for fermat theorem


coderslegacy:
20180424 02:13:40
strictly use Fermat Theorem costed me 2 TLE


kkislay20:
20180117 18:02:27
I did the c++ implementation of fermat method but got TLE. Any suggestions would be appreciated. 

sandeep_123:
20171214 13:48:24
80 :D !!


vishesh197:
20170820 12:33:33
use bruteforce with bit of optimization and do it in O(sqrt(n))


evoiz963:
20170721 11:56:19
brute force

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