FYT Training Portal

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¹².

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