Isn't ancient Egypt absolutely fascinating? The inspiring architecture, mystical culture, and stunning fashion sense make it a place worth spending a whole day or two exploring.

Luckily, you don't have to just dream it! You and your friends recently got your hands on one of Adelaide University's latest inventions: the Prime Machine. This incredible time machine lets you travel back to any year that is a prime number.

Note: A prime number is a number greater than 1 that is only divisible evenly by 1 and itself. For example, 5 is prime, but 6 is not, because it can be divided into 2 groups of 3.

Annoyingly, your friends can't agree on which year to visit: each has picked some year (BC). For each of these years, determine whether the Prime Machine can take you there, that is, whether the year is a prime number.

Note: Number ~A~ is divisible by number ~B~ if and only if \(A \: \% \: B = 0\).

Input

The first line contains a single integer, ~n~ (~1 \leq n \leq 10^3~), the number of friends who are going to travel with you.

The next line contains ~n~ integers ~y_1\ \dots\ y_n~ (~30 \leq y_i \leq 3100~), where ~y_i~ is the year that your ~i~th friend wants to travel to.

Output

For each proposed year, output "Yes" if the prime machine can take you there, that is, if that year is a prime. Otherwise output "No". Each output should be on its own line.

Example

Input 1

3
30 2763 67

Output 1

No
No
Yes

~30~ is not prime, ~30 = 10 \times 3~. ~2763~ is not prime, ~2673 = 81 \times 33~. ~67~ is prime.

Input 2

8
3100 3100 30 31 40 41 50 51

Output 1

No
No
No
Yes
No
Yes
No
No