Sau khi thành thạo sàng Eratosthenes, Yunzi tự tin rằng không số nguyên tố nào làm khó được mình. Thầy giáo mỉm cười và đưa ra một danh sách các con số khổng lồ — lớn đến mức không thể sàng, cũng không thể chia thử từng ước.

Cho ~T~ số nguyên, với mỗi số hãy cho biết nó có phải số nguyên tố hay không.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~T~ — số lượng truy vấn.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~a~.

Kết quả

Với mỗi số, in ra trên một dòng YES nếu số đó là số nguyên tố, ngược lại in ra NO.

Ví dụ

Đầu vào:

5
1
2
561
999999999999999989
1000000000000000000

Đầu ra:

NO
YES
NO
YES
NO

Giải thích: Số ~1~ không phải số nguyên tố. Số ~2~ là số nguyên tố chẵn duy nhất. Số ~561 = 3 \times 11 \times 17~ là hợp số — đây là số Carmichael nhỏ nhất, nổi tiếng vì đánh lừa phép thử Fermat với hầu hết cơ số. Số ~999999999999999989~ là số nguyên tố lớn nhất không vượt quá ~10^{18}~.

Giới hạn

• ~1 \le T \le 10^5~
• ~1 \le a \le 10^{18}~

Chia thử đến ~\sqrt{a}~ tốn ~10^9~ phép chia cho một số nguyên tố cỡ ~10^{18}~, chắc chắn quá thời gian. Hãy dùng thuật toán Miller-Rabin: viết ~a - 1 = 2^k \cdot m~ với ~m~ lẻ, rồi kiểm tra điều kiện ~x^m \equiv 1~ hoặc ~x^{2^l m} \equiv -1 \pmod a~ với từng cơ số ~x~. Với bộ cơ số ~\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}~, kết quả đã được chứng minh là chính xác tuyệt đối cho mọi ~a < 2^{64}~.

Chú ý bẫy tràn số: ~a~ lên đến ~10^{18}~ nên tích hai số dư trong quá trình lũy thừa vượt quá long long — hãy dùng __int128 cho phép nhân trung gian.