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
krish3d2y: 2019-11-20 00:24:41

AC with precomputation and binary search!! :)

killer_knight: 2019-09-29 14:18:57

make sure to use every variable as long long..costed me 1 WA :(

prashantpx_1: 2019-07-16 07:26:56

Take care of "NO" I got 1 WA for that.

sanket17: 2019-07-13 08:51:04

hint: Sometime typecating is very useful

tanav_shah1: 2019-03-26 15:40:53

Nice Problem, AC in 1 go!

dev_gupta01: 2019-02-01 15:10:08

take care it's "No" not "NO"

sea_26: 2018-11-21 09:36:09

Accepted in one go.Using Fermat's theorem on sums of two squares.TC O(sqrt(n))

sea_26: 2018-11-21 09:35:13

Accepted in one go.Using Fermat's theorem on sums of two squares.

tanardi gunawan: 2018-09-06 12:35:45

if someone comment ac with brute force , that is sh1t , using fermat can ac

prince_jain: 2018-06-28 01:52:42

weak test cases my code gives yes to 77 instead of giving no


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