Determine whether each queried number is prime.

Input

The first line contains \(T\) followed by \(T\) queried integers.

The input satisfies:

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

Output

Print YES or NO for each query on its own line.

Example

Input

2
493759
601316

Output

NO
NO