Problem: We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

Output

Print n lines: the i-th line should contain "YES" (without the quotes), if number xi is Т-prime, and "NO" (without the quotes), if it isn't.

Examples

Input

3
4 5 6


Output

YES
NO
NO

Note

The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".

Solution (in PYTHON3):

Solution:
'''
T-Primes (1300 Rating).

We know that each number has atleast 2 positive divisors(1 and itself)
To find numbers with only 3 positive divisors, we can only add 1 more divisor to our existing list of 2.

Since 1 * x = x, let the 3rd divisor be y.
Since y != 1 or x, we cannot have 1*y = x or x*y = x
Therefore, the only way y is a positive divisor for x is if y * y = x

Therefore, for each input in the list, check if it is a perfect square.
This is only the first condition.
From here, we need y to be a prime #. 
If y is not prime, then x has more than 3 divisors. (Invariant).

We will solve this problem with Case Analysis(Problem Solving Technique)
1) If a number is even and is not 4, then output NO. The reason 4 works is because we have 1,2,4 as the divisors.

2) If a number is odd and a perfect square, check if the square root is prime or not. If it is , then output YES, otherwise output NO.

Runtime can be improved by building a list of primes.
Since the largest # is going to be 10^12, we only need to store primes up to <= 10^6 since the square root will be at most 10^6.
With this list of primes, we can check if a number is prime in O(1) time.

Runtime will be O(n) and constant time to build the prime table.
'''
import math
def solve(elem):
    if elem == 4:
        return 'YES'
    if elem % 2 == 0 or elem == 1:
        return 'NO'
    root = math.sqrt(elem)
    if int(root)*int(root) == elem and primes[int(root)]:
        return 'YES'
    return 'NO'

primes = [True] * (1000000 + 1)
for i in range(2, 1000000 + 1):
    if primes[i] == False:
        continue
    for j in range(i*i, 1000000 + 1, i):
        primes[j] = False

n = int(input())
arr = list(map(int, input().split(' ')))
for elem in arr:
    print(solve(elem))