B. Braga's Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Asp Of R/2 Braga is eager to graduate from the Institute of Mysterious Experiments, also known as IME, and he realized that there are only 193 days until graduation!

Also, he realized something even more interesting:

$$$193$$$ is prime.

There are $$$43$$$ prime numbers in the range $$$[2, 193)$$$.

$$$43$$$ is prime.

There are $$$13$$$ prime numbers in the range $$$[2, 43)$$$.

$$$13$$$ is prime.

There are $$$5$$$ prime numbers in the range $$$[2, 13)$$$.

$$$5$$$ is prime.

There are $$$2$$$ prime numbers in the range $$$[2, 5)$$$.

$$$2$$$ is prime, and the sequence is finished now as $$$2$$$ is the lowest prime number.

His brain is melting with this fascinating discovery and he decided to call this day beautiful.

Now he wonders which days could also be considered beautiful. So he asks you $$$q$$$ questions, each of them a number $$$n$$$, wondering if $$$n$$$ can be considered a beautiful day or not.

Input

The first line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the amount of questions that Braga asks.

The next $$$q$$$ lines will contain a single integer $$$n$$$ $$$(2 \leq n \leq 10^7)$$$ — the day that Braga wonders is beautiful or not.

Output

For each question, print out YES if it's a beautiful day and NO otherwise.

You may output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will be accepted as a positive answer.

Example
Input
7
1181
55
193
3
43
5
7
Output
YES
NO
YES
NO
YES
YES
NO