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:
'''
def main():
    from sys import stdin,stdout
if __name__=='__main__':
    main()
'''
#118B
'''
def main():
    from sys import stdin,stdout
    n=int(stdin.readline())
    for i in range(n+1):
        stdout.write(' '*(2*(n-i)))
        for k in range(i+1):
            if k:
                if k==1:
                    stdout.write(' 1 ')
                else:
                    stdout.write(str(k)+' ')
            else:
                stdout.write('0')
        for k in range(i-1,-1,-1):
            if k:
                stdout.write(str(k)+' ')
            else:
                stdout.write('0')
        stdout.write('')
    for j in range(i-1,-1,-1):
        stdout.write(' '*2*(n-j))
        for k in range(j+1):
            if k:
                if k==1:
                    stdout.write(' 1 ')
                else:
                    stdout.write(str(k)+' ')
            else:
                stdout.write('0')
        for k in range(j-1,-1,-1):
            if k:
                stdout.write(str(k)+' ')
            else:
                stdout.write('0')
        stdout.write('')
if __name__=='__main__':
    main()
'''
#499B
'''
def main():
    from sys import stdin,stdout
    n,m=map(int,stdin.readline().split())
    mydic={}
    for _ in range(m):
        a,b=map(str,stdin.readline().strip().split())
        mydic[a]=b
    for k in stdin.readline().strip().split():
        if len(mydic[k])<len(k):
            stdout.write(mydic[k]+' ')
        else:
            stdout.write(k+' ')
if __name__=='__main__':
    main()
'''
#450A
'''
def main():
    from sys import stdin,stdout
    n,m=map(int,stdin.readline().split())
    k=list(range(1,n+1))
    a=list(map(int,stdin.readline().split()))
    while k!=[]:
        top=k[0]
        if a[top-1]<=m:
            k=k[1:]
            a[top-1]=0
        else:
            a[top-1]-=m
            k=k[1:]+[top]
    stdout.write(str(top))
if __name__=='__main__':
    main()
'''
#550C
'''
def main():
    from sys import stdin,stdout
    n=stdin.readline().strip()
    i=0
    k=2
    t=''
    for j in n[::-1]:
        if j=='0':
            t='0'
            break
        elif j=='8':
            tz='8'
            break
        i+=1
        if k==16:
            break
        if int(j+t) & (k-1):
            continue
        else:
            t=j+t
            k<<=1
    #print(t,i)
    if t!='':
        if int(t)%8==0:
            if i!=len(n) and t!='0' and t!='8':
                stdout.write('YES\n'+n[:len(n)-i+1]+t)
            else:
                stdout.write('YES\n'+t)
        else:
            stdout.write('NO')
    else:
        stdout.write('NO')
if __name__=='__main__':
    main()
'''
#476B
'''
def main():
    from sys import stdin,stdout
    a=stdin.readline().strip()
    b=stdin.readline().strip()
    apc=0
    anc=0
    bpc=0
    bnc=0
    bqc=0
    for i in a:
        if i =='+':
            apc+=1
        elif i=='-':
            anc+=1
    for i in b:
        if i=='+':
            bpc+=1
        elif i=='-':
            bnc+=1
        else:
            bqc+=1
    #print(apc,anc,bpc,bnc,bqc)
    if apc==bpc and anc==bnc and bqc==0:
        p=1
    elif bpc>apc or bnc>anc or len(a)!=len(b):
        p=0
    else:
        denom=(1<<bqc)
        numer=1
        maxim=max(apc-bpc,anc-bnc)
        minim=min(aspc-bpc,anc-bnc)
        while(bqc>maxim):
            #print(numer)
            numer*=bqc
            bqc-=1
        if minim>1:
            k=minim
            while(minim>=2):
            #print('k',k)
                k*=(minim-1)
                minim-=1
            numer/=k
        p=numer/denom
    stdout.write('{:.12f}'.format(p))
if __name__=='__main__':
    main()
'''
'''
def main():
    from sys import stdin,stdout
    for _ in range(int(stdin.readline())):
        l1,l2,l3,n=stdin.readline().strip().split()
        L=l1+l2*int(n)+l3
        n=int(L,2)
        c=0
        while n>=0:
            n=(n&(n+1)) -1
            #print(n)
            c+=1
        stdout.write(str(c)+'\n')
if __name__=='__main__':
    main()
'''
#230B
'''
def main():
	from sys import stdin,stdout
	s=[]
	for i in range(1000000):
		s.append(True)
	for i in range(2,1000000):
		if s[i-1]:
			j=2*i
			while j<=1000000:
				s[j-1]=False
				j+=i
	#print(s[:10])
	t=int(stdin.readline())
	for i in stdin.readline().strip().split():
		n=int(i)
		k=n**0.5
		if int(k)==k and s[int(k)-1] and n!=1:
			stdout.write('YES\n')
		else:
			stdout.write('NO\n')
if __name__=='__main__':
	main()
'''
#489C
'''
def main():
	import sys
	a,b=map(int,sys.stdin.readline().split())
	if not a:
		maxim='-1'
		minim='-1'
	elif not b:
		if a==1:
			maxim='0'
			minim='0'
		else:
			maxim='-1'
			minim='-1'
	else:
		#finding the maximum number	
		maxim=0
		n=b
		while n:
			if 9>n:
				maxim=maxim*10+n
				n=0
			else:
				n-=9
				maxim=maxim*10+9
		s=str(maxim)
		diff=a-len(s)
		if diff<0:
			maxim='-1'
		elif diff>0:
			maxim=s+'0'*diff
		else:
			maxim=s
		#finding the minimum number
		if diff:
			if diff<0:
				minim='-1'
			else:
				s=maxim[::-1]
				for i in range(len(s)):
					if int(s[i]):
						break
				
				minim='1'+'0'*(i-1)+str(int(s[i])-1)+s[i+1:]
		else:
			minim=maxim[::-1]
	sys.stdout.write(minim+' '+maxim+'\n')
if __name__=='__main__':
	main()
'''
#230B
def main():	
	import sys
	import bisect
	C=int(1e6)
	l=[]
	for i in range(C):
		l.append(True)
	for i in range(3,C,2):
		if l[i-1]:
			j=3*i
			while j<=C:
				l[j-1]=False
				j+=2*i
	for i in range(3,C,2):
		l[i]=False
	l[0]=False
	s=[]
	for i in range(C):
		if l[i]:
			s.append((i+1)*(i+1))
	#print(s[:10])
	n=int(sys.stdin.readline())
	tup=tuple(map(int,sys.stdin.readline().split()))
	for i in tup:
		pos=bisect.bisect_left(s,i)
		if pos!=len(s) and s[pos]==i:
			sys.stdout.write('YES\n')
		else:
			sys.stdout.write('NO\n')
	#print(s[:10])
if __name__=='__main__':
	main()