Một số nguyên dương được gọi là số ba ước nếu nó có đúng ba ước dương phân biệt. Cho ~N~ số nguyên dương ~x_1, x_2, ..., x_N~.

Với mỗi ~x_i~, hãy xác định số đó có phải số ba ước hay không.

Input

• Dòng đầu chứa số nguyên ~N~, là số lượng giá trị cần kiểm tra.
• Dòng thứ hai chứa ~N~ số nguyên ~x_1, x_2, ..., x_N~.

Output

• In ~N~ dòng; dòng thứ ~i~ là YES nếu ~x_i~ có đúng ba ước dương, ngược lại là NO.

Giới hạn

• ~1 ≤ N ≤ 10^5~.
• ~1 ≤ x_i ≤ 10^{12}~ với mọi ~1 ≤ i ≤ N~.

Ví dụ

Input

3
4 5 6

Output

YES
NO
NO

Giải thích ví dụ

Số 4 có đúng ba ước dương là 1, 2, 4 nên nhận kết quả YES. Số 5 chỉ có hai ước là 1, 5; số 6 có bốn ước là 1, 2, 3, 6, nên cả hai nhận kết quả NO.