Problem: Mr. Retardo has lost his marbles. He's a professor, and absolutely loathes his students. And since going full retard, he asks them all sorts of useless questions. His latest obsession is prime numbers, and he gives all his a students random number n and asks them to check if it is prime. 
Check if it is!!

Note that the permitted language list for this problem has been altered. Please check before solving.

EDIT

Maximum number of test cases - 500,
0 ≤ n ≤ 5*10^9

SAMPLE INPUT
5

2
3
4
5
6

SAMPLE OUTPUT
YES
YES
NO
YES
NO

Solution (in PYTHON):

Solution:
from bisect import bisect_left
def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

__primes=primes(70710)
def is_prime(n):
    # if prime is already in the list, just pick it
    if n <= 70710:
        i = bisect_left(__primes, n)
        return i != len(__primes) and __primes[i] == n
    # Divide by each known prime
    limit = int(n ** .5)
    for p in __primes:
        if p > limit: return True
        if n % p == 0: return False
    # fall back on trial division if n > 1 billion
    for f in range(70710, limit, 6): # 70710 is the next prime
        if n % f == 0 or n % (f + 4) == 0:
            return False
    return True
t=int(raw_input())
raw_input()
for test in xrange(t):
	n=int(raw_input())
	if is_prime(n):
		print 'YES'
	else:
		print 'NO'