For each given integer, determine whether it is prime.

Input

The first line contains \(T\). Each of the next \(T\) lines contains \(n\).

The input satisfies:

• \(1 \le T \le 10^4\)
• \(0 \le n \le 10^7\)

Output

For each query, print YES if \(n\) is prime; otherwise, print NO.

Example

Input

9
8840528
7748181
5244227
9965931
5729253
2554560
3803974
9902232
8167203

Output

NO
NO
NO
NO
NO
NO
NO
NO
NO