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:
import math
n=int(input())
data=list(map(int,input().split()))
#max=data[0]
#for x in data:
#    if x>max:
#        max=x

basicprime=[3, 5, 517, 7, 521, 11, 523, 13, 527, 17, 529, 19, 533, 23, 29, 541, 31, 547, 37, 551, 41, 43, 557, 47, 559, 563, 53, 569, 59, 571, 61, 577, 67, 71, 583, 73, 587, 589, 79, 593, 83, 599, 89, 601, 607, 97, 611, 101, 613, 103, 617, 107, 619, 109, 113, 629, 631, 121, 127, 641, 131, 643, 647, 137, 649, 139, 653, 143, 659, 149, 661, 151, 667, 157, 671, 673, 163, 677, 167, 169, 683, 173, 689, 179, 691, 181, 697, 187, 701, 191, 703, 193, 197, 709, 199, 713, 719, 209, 211, 727, 731, 221, 733, 223, 737, 227, 739, 229, 743, 233, 239, 751, 241, 757, 247, 761, 251, 253, 767, 257, 769, 773, 263, 779, 269, 781, 271, 787, 277, 281, 793, 283, 797, 799, 289, 803, 293, 809, 299, 811, 817, 307, 821, 311, 823, 313, 827, 317, 829, 319, 323, 839, 841, 331, 337, 851, 341, 853, 857, 347, 859, 349, 863, 353, 869, 359, 871, 361, 877, 367, 881, 883, 373, 887, 377, 379, 893, 383, 899, 389, 901, 391, 907, 397, 911, 401, 913, 403, 407, 919, 409, 923, 929, 419, 421, 937, 941, 431, 943, 433, 947, 437, 949, 439, 953, 443, 449, 961, 451, 967, 457, 971, 461, 463, 977, 467, 979, 983, 473, 989, 479, 991, 481, 997, 487, 491, 493, 499, 503, 509]

#m=math.ceil(math.sqrt(max))
prime=set(i for i in range(3,1000000,2))
prime.add(2)
#for i in range(2,m+1):
#    prime.add(i)


for i in basicprime:
    for j in range(3,333334,2):
    #for j in range(2,m//2+1):
        #if j*i<=m:
            #if i*j in prime:
        d=i*j
        if d < 1000000:
            if d in prime:
                prime.remove(d)
        else:
            break

for x in data:
    if x == 1 or x == 2 or x == 3:
        print("NO")
    else:
        q = math.sqrt(x)
        if q % 1 == 0.0:
            print(["NO","YES"][q in prime])
        else:
            print("NO")