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:
import random
def modulo(a,b,c):
        x = 1
        y = a
        while b>0:
                if b%2==1:
                        x = (x*y)%c
                y = (y*y)%c
                b = b/2
        return x%c
         
def mi(N,iteration):
        if N<2:
                return 0
        if N!=2 and N%2==0:
                return 0
         
        d=N-1
        while d%2==0:
                d = d/2
         
        for i in range(iteration):
                a = random.randint(1, N-1)
                temp = d
                x = modulo(a,temp,N)
                while (temp!=N-1 and x!=1 and x!=N-1):
                        x = (x*x)%N
                        temp = temp*2
                 
                if (x!=N-1 and temp%2==0):
                        return 0
         
        return 1
        
test=input()
q=raw_input()
for x in range(test):
	n=raw_input()
	test=test+1
	if(n):
		test=test-1
		#print n
		k=int(n)
		if(mi(k,100)==1): 
			print "YES"
		if(mi(k,100)==0):
			print "NO"