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
numerix: 2014-10-07 16:15:13

My former AC code now results in INTERNAL ERROR. Can that be checked, please?

S: 2014-09-26 10:11:29

leant a lot from this :D

vikrant: 2014-09-21 12:44:56

can u please check my submission with Id:12422611

mohan kumar: 2014-06-22 13:58:22

i am getting time limit exceedence,any one
please find the mistake with this code
http://www.spoj.com/submit/TWOSQRS/id=11806674

Rahul Ranjan: 2014-06-04 08:05:41

<snip>
what's wrong with the code....getting SIGFPE but cud not find the error...plz help.....

Last edit: 2022-08-18 18:05:05
`Ak: 2014-05-27 16:28:13

finally got AC :)

suryasis: 2014-03-11 09:06:53

c*sqrt(n) tle wtf

Unknown: 2014-02-06 06:47:40

interesting one..!!!

Daga: 2014-01-14 07:50:55

Not accepting in sqrt(n) ... Tle

Last edit: 2014-01-14 07:51:23
SanchitK: 2013-12-16 13:06:25

giving WA even it works for all the cases. please check my <snip>

Last edit: 2022-08-18 18:05:01

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