SPOJ 91 - TWOSQRS Solution

Difficulty: Easy
Problem: 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

Explanation

There's multiple way to solve this problem such as prime factorization, Fermat's Theorem, and brute force approach. In brute force approach, you can solve this problem by trying all possible sum of squares between 0 up to square of n.

Source Code