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.
from sympy import isqrt, sieve, symbols, sqrt, Matrix, mod_inverse

def quadratic_sieve(n):
    # 步骤1：选择合适的参数
    k = isqrt(n) + 1  # 取平方根
    m = 2 * k  # 选择矩阵的列数

    # 步骤2：生成平方数集合
    primes = list(sieve.primerange(2, k + m))
    squares = [prime * prime for prime in primes]

    # 步骤3：构建矩阵
    # 创建变量
    x = symbols('x')
    # 构建多项式
    f = x * x - n
    # 计算多项式的值
    values = [f.subs(x, x_i) for x_i in range(k, k + m)]
    # 构建矩阵
    matrix = Matrix([[values[j] % prime for prime in primes] for j in range(m)])

    # 步骤4：高斯消元
    reduced, pivots = matrix.rref()

    # 步骤5：找到平方因子
    for row in reduced:
        factor = 1
        for i, pivot in enumerate(pivots):
            if i < m and row[i] % 2 == 1:
                factor *= squares[pivot]
        if factor % n != 0:
            y = isqrt(factor)
            p = gcd(n, y + factor)
            q = n // p
            return p, q

    return None, None

n = int(input())
nums = list(map(int, input().split()))

for num in nums:
    if num == 1:
        print('NO')
        continue

    p, q = quadratic_sieve(num)
    if p is not None and q is not None:
        print("YES")
    else:
        print("NO")