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
YesScoring
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.