Khóa ba chìa

Một chiếc két chỉ mở được bằng mã khóa là số Sphenic: số nguyên dương viết được thành tích của đúng ba số nguyên tố phân biệt. Ví dụ 30 = 2 × 3 × 5 và 1001 = 7 × 11 × 13 là số Sphenic; 60 = 2² × 3 × 5 (có thừa số lặp), 210 = 2 × 3 × 5 × 7 (bốn thừa số) và 1 thì không.

Cho T mã khóa, hãy cho biết từng mã có mở được két hay không.

Với N lên tới 10^12 không thể thử chia cho mọi số từ 2 đến N; hãy phân tích N thành thừa số nguyên tố một cách hiệu quả.

Input

• Dòng 1: số nguyên T.
• T dòng sau, mỗi dòng một số nguyên dương N.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10^12

Output

Với mỗi mã, in một dòng YES nếu N là số Sphenic, ngược lại in NO.

Ví dụ

Ví dụ 1

Input

4
30
60
1001
1

Output

YES
NO
YES
NO