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
Deepanshu: 2013-07-11 15:27:22

my code is taking 0.0 sec to run on ideone compiler but the spoj judge is showing TLE

Aasheesh Verma: 2013-07-04 17:04:18

nice one...

sacoder9114: 2013-06-22 20:01:31

again and again TLE...

Jagatheesvaran Palanisamy: 2013-04-05 14:43:59

Learnt a lot ...Use Prime factor Method..And think about how many primes u want to precompute.Finally think what will do if the prime exceeds the bound,,

fawaz ibrahim: 2013-03-29 19:14:33

oh my god ... <<<TLE>>>

phoenix: 2013-03-27 20:00:37

why does it say no to 2? isnt 2=1^2+1^2?
--ans(francky)--> 10 is the the number of test cases, not a case. So for 2, the answer is well YES.

Last edit: 2013-03-27 22:02:58
Ouditchya Sinha: 2013-03-19 16:15:08

Good Question! Learnt a lot today... :)

shashank: 2013-03-14 05:47:28

time limit exceding ?
help..

aqfaridi: 2013-02-25 09:54:29

@Pawel Gawrychowski
for(int i=2; i*i <= n ;i++) >> gives TLE
for(long long i=2; i*i <= n ;i++) >> AC
what is the reason ??
ohhh .. i got it now :)

Last edit: 2013-02-25 10:19:40
The Mundane Programmer: 2013-02-18 01:51:25

Mathematical one......


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