Benny noticed a random property of numbers. The numbers which followed this property were called as interesting numbers by Benny. Let's dive into what Benny discovered about these numbers.

1 is an interesting number.

For every N > 1 , N is interesting if it has odd number of interesting proper divisors.
For example, 2 and 3 are interesting numbers, but 4 is not interesting.

You are given T integers. For each given integer, you have to determine whether it is interesting or not.  

Input

The first line of the input contains an integer T denoting the given integers.
The next T lines contain a single integer X

Output

For each number in a single line, print "Yes" if the number is interesting and "No" otherwise (without quotes).

Constraints
1 ≤ T ≤ 5000
1 ≤ X ≤ 10^{11}

Note
25% of the test files have X ≤ 10^{6}. 

SAMPLE INPUT
5
1
2
3
4
5

SAMPLE OUTPUT
Yes
Yes
Yes
No
Yes

Explanation

In the given sample case, all numbers from 1 to 5, except 4, are interesting. The number '4' has two proper divisors and both of them are interesting. Hence, it has even number of interesting proper divisors.
def rwh_primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

def test(a, primes):
  for p in primes:
    n = 0
    while (a % p) == 0:
      n += 1
      a = a // p
    if n > 1:
      return False
    if a == 1:
      break	
  return True

primes = rwh_primes(350000)

T = int(raw_input())
for t in range(T):
  n = int(raw_input())
  if test(n, primes):
    print("Yes")
  else:
    print("No")