Primality Test

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether each of up to 10 numbers up to 100000000 is prime and print YES or NO.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

An integer $P$ greater than 1 is a prime number when it has no positive divisor other than 1 and $P$ itself. The numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 are all prime. A natural number that is at least 2 and is not prime, such as 4, 6, or 16, is a composite number. The number 1 is neither prime nor composite.

Decide whether a given natural number $N$ is prime.

Input

Read from standard input. The first line contains the number of test cases $T$ . Each of the next $T$ lines contains one natural number $N$ to test. The bounds are $1 \le T \le 10$ and $1 \le N \le 10^8$ .

Output

Write to standard output. For each test case print one line: YES when $N$ is prime, NO when it is not. There are $T$ test cases, so the program prints $T$ lines in total.

Examples2

Example 1
Input
```
3
7
15
31
```
Expected output
```
YES
NO
YES
```
Example 2
Input
```
2
1
2
```
Expected output
```
NO
YES
```