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
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
babur: 2017-06-29 05:39:34

Try using 2 pointer...simple AC in 1 go

prabodh prakash: 2017-05-07 11:40:55

Bad observational skills costed me 3 TLE. I should have tested huge numbers before submitting my solution. Not a brute force solution.

anurag_tangri: 2017-03-30 21:37:24

AC USING BRUTE FORCE :)

rv404674: 2017-03-24 19:38:23

AC in 0.00 using fermat

cake_is_a_lie: 2017-02-15 01:21:07

The given tests have the funny property that they can all pass even when you consider 2 as your only prime number. Sadistic. Cost me a WA because of a super silly mistake.


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