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
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

nvdrag123: 2018-06-27 12:18:34

use i<sqrt(n) instead of i * i< n in for loop for fermat theorem

coderslegacy: 2018-04-24 02:13:40

strictly use Fermat Theorem costed me 2 TLE

kkislay20: 2018-01-17 18:02:27

I did the c++ implementation of fermat method but got TLE. Any suggestions would be appreciated.

sandeep_123: 2017-12-14 13:48:24

80 :D !!
Brute force (*-*) complexity - O(sqrt(n)*t)

vishesh197: 2017-08-20 12:33:33

use bruteforce with bit of optimization and do it in O(sqrt(n))

evoiz963: 2017-07-21 11:56:19

brute force
O(sqrt(n));

Last edit: 2017-07-21 11:56:35

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