Chúng ta đã quá quen thuộc với khái niệm số nguyên tố. Một số nguyên tố là số nguyên dương lớn hơn \(1\) và có đúng hai ước dương là \(1\) và chính nó.

Để làm mới bài toán, hôm nay ta định nghĩa một số TPrime là một số nguyên dương lớn hơn \(1\) và có đúng \(3\) ước dương.

Cho \(n\) truy vấn, mỗi truy vấn là một số nguyên dương \(a\). Với mỗi truy vấn, hãy kiểm tra xem \(a\) có phải là số TPrime hay không.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 3 \cdot 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a\) (\(1 \le a \le 10^{12}\)).

Output

• In ra \(n\) dòng. Với mỗi truy vấn, in ra YES nếu \(a\) là số TPrime, ngược lại in ra NO.

Example

3
4
6
7

YES
NO
NO

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 100, 1 \le a \le 10^4\).
• Subtask \(2\) (\(40\%\) số điểm): \(1 \le n, a \le 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.