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
avinash: 2013-11-04 10:17:17

can anyone help me with my code ? here is the link <snip>

Last edit: 2022-08-18 18:04:56
avinash: 2013-11-04 10:16:24

what is c in O(c*sqrt(n))?

anshul garg: 2013-10-29 09:45:12

@Pulkit Jain. My Solution is c*sqrt(n)
But its TLE

innovolt: 2013-10-20 05:53:13

too easy if u get that idea (no prime factor,no prime precompute)...just very basic and i got AC

Garima: 2013-10-18 19:22:17

Somebody please check my code,am getting wrong answers for some numbers like 2888
<snip>

Last edit: 2022-08-18 18:04:52
Pulkit Jain: 2013-09-04 15:24:09

O(sqrt(n)) solution accepted \m/

(Tjandra Satria Gunawan)(曾毅昆): 2013-08-22 22:16:59

@joud zouzou: My O(c*sqrt(n)) algo is TLE too. And yes there's better solution, my AC algo is O(2*c*(sqrt(n)/ln(n)))

joud zouzou: 2013-08-18 07:50:12

why is SPOJ so slow??
my solution take O(c*sqrt(n)) is there a better solution?

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


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