Vicky has great love for gardening and prime numbers. He wants to create a rectangular garden such that the square of the diagonal of the rectangle is a prime number (the diagonal of course can be any real number) and its sides are positive integers. You have to help Vicky by telling whether he can create such a garden or not, for the given value of square of diagonal.

Input
Number of test cases T( ≤ 10^6) followed by T lines of numbers having possible values of square of diagonal (a prime number between 1 and 10000000).

Output
T lines with “YES” to denote the corresponding value is possible and “NO” to denote negative response (without quotes).

Example

Input:
1
2

Output:
YES

Explanation:
2 = 1^2 + 1^2

见题面

见题面