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.
The first line contains a single positive integer, *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), showing how many numbers are in the array. The next line contains *n* space-separated integers *x*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">12</sup>).

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.

# Version 21.0
import os, sys, math, itertools
from collections import deque, defaultdict, OrderedDict, Counter
from bisect import bisect, bisect_left, bisect_right, insort
from heapq import heapify, heappush, heappop, nsmallest, nlargest, heapreplace, heappushpop

offline = __debug__
if not offline:
    import io
    input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

ii = lambda : int(input())
si = lambda : input()               
mi = lambda : map(int,input().strip().split(" "))
msi = lambda : map(str,input().strip().split(" ")) 
li = lambda : list(mi())
lsi = lambda : list(msi())
out = []
export = lambda : sys.stdout.write('\n'.join(map(str, out)))
p = lambda x : out.append(x)
pp = lambda array : p(' '.join(map(str,array)))

def main() -> None:
    # 2023-10-21 21:35:32


    n = int(1e6)
    l = [True] * n
    s = set()
    for i in range(2,n):
        if l[i]:
            s.add(i*i)
            for j in range(i*i,n,i):
                l[j] = False
    length = ii()
    ll = li()
    for x in ll:
        if x not in s:
            p('NO')
        else:
            p('YES')
    
try: exec('from hq import *\nexec(cc)')
except (FileNotFoundError, ModuleNotFoundError): main(); export()
	   		  			   					  		 	   	 	