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
t=input("")
while t:
  t=t-1
  a=input("")
  if(a==2):
    print "YES"  
  elif(a%4==1):
    print "YES"
  else:
    print "NO"