밀러-라빈 소수 판별

제한

• $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$은 소수가 아님에 유의하라.