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
Luis Herrera: 2016-05-30 04:56:56

Solved using fermat theorem.

Michal Idzikowski: 2016-03-03 03:49:57

Can you tell me what is wrong with my answers #16411672 #16411678?
I tried multiple values and it works good. Return same result as written here.

EDIT: Found it. There was a problem with reading number count, I needed to add '\n' in scanf for int.

Last edit: 2016-03-03 04:03:22
Vicky: 2016-02-21 13:31:27

Don't think too much :p

hulk_baba: 2016-02-13 19:33:27

one important properties of such number is key to problem,
(related to prime factors.)

uday pratap verma: 2016-02-07 11:27:18

using seive algorithm to solve it.....

dokz: 2016-01-15 12:17:52

NVM Wrong comment.

Last edit: 2016-01-15 12:18:33
refresh: 2015-12-30 12:38:50

my id is 15973062...can anyone tell me the error in my code or some testcases would be better!

Last edit: 2015-12-31 03:43:55
ashu05: 2015-12-22 06:00:57

tried using fermat's theorem but costed me 1 WA

ankitch6: 2015-12-18 16:16:37

using int cost me 4 four wrong answers:(

norhh: 2015-10-22 10:55:31

0.14 s AC by brute force with 30 lines.using theorem i think its a bit hard to implement.


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