밀러-라빈 소수 판별

문제

T개의 쿼리가 주어진다. 각 쿼리마다 양의 정수 N이 소수인지 판별하여 그 결과를 출력하라.

단, $N$의 범위가 최대 $10^{18}$으로 매우 크기 때문에 $O(\sqrt{N})$ 시간 복잡도의 일반적인 소수 판별법으로는 시간 내에 해결할 수 없다. 밀러-라빈(Miller-Rabin) 소수 판별법과 같은 확률적 또는 결정적 빠른 소수 판별법을 활용하여 문제를 해결해야 한다.

입력

첫째 줄에 쿼리의 개수 T가 주어진다.
둘째 줄부터 T개의 줄에 걸쳐 각 줄마다 소수인지 판별할 양의 정수 N이 하나씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 10^{18}$
• 밀러-라빈 판별법을 사용할 때, $N \le 10^{18}$ 범위 내의 모든 수에 대해 오차 없이 정확한 결과를 보장하려면 특정 작은 소수들(예: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)을 밑으로 사용하는 것으로 충분하다.
• 엣지 케이스로 주어지는 $N = 1$은 소수가 아님에 유의하라.

출력

각 쿼리에 대하여 주어진 N이 소수이면 "YES", 소수가 아니면 "NO"를 한 줄에 하나씩 출력한다.

예제 입력 1

5
2
4
17
97
1000000007

예제 출력 1

YES
NO
YES
YES
YES

예제 입력 2

3
1000000000000000000
1000000000000000009
999999999999999877

예제 출력 2

NO
YES
YES