Mã có đúng ba ước

Bối cảnh và bài toán

Một hệ thống kiểm định sử dụng một loại mã đặc biệt: mã được chấp nhận khi số nguyên đại diện cho mã có đúng ba ước dương phân biệt. Một lô dữ liệu chứa rất nhiều mã, và mỗi mã có thể rất lớn.

Bạn cần xác định nhanh mã nào đạt tiêu chuẩn.

Yêu cầu

Với mỗi số x[i], in YES nếu nó có đúng ba ước dương phân biệt, ngược lại in NO.

Input

• Dòng 1: số nguyên n.
• Dòng 2: n số nguyên dương x[i].

Output

In n dòng, mỗi dòng là YES hoặc NO tương ứng với một mã.

Ràng buộc

• 1 <= n <= 10^5
• 1 <= x[i] <= 10^12

Chấm điểm

Ví dụ 1

Input

3
4 5 6

Output

YES
NO
NO

Giải thích. 4 có các ước 1,2,4; 5 có hai ước, còn 6 có bốn ước.

Ví dụ 2

Input

4
9 16 25 49

Output

YES
NO
YES
YES

Giải thích. 9=3^2, 25=5^2, 49=7^2 đều có đúng ba ước; 16 có năm ước.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces Round 142 (Div. 2), B. T-primes (230B). Tham khảo: https://codeforces.com/problemset/problem/230/B