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
BOND: 2013-01-25 08:04:00

naive fermat's won't pass...

saket diwakar: 2013-01-16 16:57:41

easy one....:)

Philipp Heeg: 2012-12-25 16:53:30

2888 = 2 38²

gourav: 2012-12-06 16:47:53

awesome things i have learnt while doing this single question...hats off my mathematicians.. :-)

750: 2012-11-25 01:01:38

2888 ?¡?¡?¡
Creo que no se puede.

Asheesh Ranjan: 2012-10-12 15:46:58

<snip>
Why WA ? I cant find any cases >:(

Last edit: 2022-08-18 18:04:42
Panagiotis Kostopanagiotis: 2012-09-08 18:25:11

O(K*sqrt(N)) but i get TLE error, i think it's the optimal solution :/

dev2: 2012-08-14 08:30:50

how 2888 is written in form of sum of the square of two number ?plzz explain...

Ishan Bhatt: 2012-05-18 15:42:45

is everyone using the prime factorization method?..mine is a O(sqrt(n)) algorithm, but still giving TLE

Darky: 2012-03-21 20:38:01

I'm getting a TLE in JAVA!


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