5 - Detecting Primes
Time limit: 1000 ms
Memory limit: 250 MB

You are given an integer N. Your task is to determine whether this number is a prime number or not.

A prime number is a number greater than 1 that cannot be divided evenly by any number other than 1 and itself. For example, 2, 3, 5, 7 are prime numbers, while 4, 6, 8 are not.

Input

  • The first line contains an integer T, the number of test cases.

  • Each of the next T lines contains a single integer N.

Output

For each test case, print YES if the number is prime, or NO if it is not (without quotes).

Constraints

  • 1 ≤ T ≤ 1000

  • 1 ≤ N ≤ 106

Example Input Example Output 
3
2
4
17
 
YES
NO
YES

Sign in to Submit