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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>

using namespace std;

int main(){
int t=0;
long long n;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
bool good = true;
for (long long i=2; i*i<n; i++){
int ct=0;
while(n%i==0){
ct++;
n/=i;
}
if(i%4==3&&ct%2==1){
good=false;
break;
}
}
if(n%4==3)good=false;
if(good) printf("Yes\n");
else printf("No\n");
}
}``````
Copy The Code &

Input

cmd
10
1
2
7
14
49
9
17
76
2888
27

Output

cmd
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No