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.
n=int(input())
def euler(n):
    global s
    i=3
    while i<n:
        if i in s:
            l=n//i
            for num in range(2,l+1):
                if num*i in s:
                    s-={num*i}
            i+=2
        else:
            i+=2
    return s

s=set([2,5]+[k for k in range(3,n,2) if str(k)[-1]!='5'])
print(euler(n))
from math import sqrt
def f(s):
    if s==4 or s==25:
        return 1
    if str(s)[-1] in ['2','3','7','6','4','0','5']:
        return 0
    if s==1:
        return 0
    t=sqrt(s)
    if int(t)!=t:
        return 0
    if t not in s:
        return 0
    return 1
l=list(map(int,input().split()))
for c in l:
    if f(c):
        print('YES')
    else:
        print('NO')