Given an integer $N$, you need to test whether $N$ is a prime number.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

For each test case, the first line of the input contains a single integer $N$ ($1 \le N \le 10^{18}$).

Output

For each test case, if the number $N$ is a prime number, output a single line with a single word Yes. Otherwise, output a single line with a single word No.

Examples

Input

5
1
2
3
4
5

Output

No
Yes
Yes
No
Yes

Scoring

For all test cases, $1 \le T \le 10^5$, $1 \le N \le 10^{18}$.

• Subtask 1 (10 points): $1 \le N \le 10^5$
• Subtask 2 (30 points): $1 \le N \le 10^9$
• Subtask 3 (60 points): No additional constraints.