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.
import math

# 设置上限N为10001
N = int(1e4 + 1)
# 假设范围内的所有数字都是素数，0和1除外
isprime = [False, False] + [True for _ in range(2, N)]

# 使用埃拉托斯特尼筛法生成素数列表
def generate_primes():
    for a in range(2, int(N**0.5) + 1):
        if isprime[a]:
            for j in range(a*a, N, a):
                isprime[j] = False

# 调用函数生成素数列表
generate_primes()

# 输入数字的数量
n = int(input())
# 输入数字列表
nums = list(map(int, input().split()))

# 对于列表中的每一个数字
for num in nums:
    # 计算数字的平方根
    root = int(num**0.5)
    # 如果数字是完全平方数且其平方根是素数
    if root * root == num and isprime[root]:
        print("YES")
    else:
        print("NO")