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 Prime_Test(number):
    
    if number == 2:
        return True
    elif number == 1 or number % 2 == 0:
        return False
    
   
    oddPartOfNumber = number - 1
    
    
    timesTwoDividNumber = 0
    
    
    while oddPartOfNumber % 2 == 0:
        oddPartOfNumber = oddPartOfNumber / 2
        timesTwoDividNumber = timesTwoDividNumber + 1 
   
    for time in range(3):
        
       
        while True:
            
            randomNumber = random.randint(2, number)-1
            if randomNumber != 0 and randomNumber != 1:
                break
        
       
        randomNumberWithPower = pow(randomNumber, oddPartOfNumber, number)
        
       
        if (randomNumberWithPower != 1) and (randomNumberWithPower != number - 1):
            
            iterationNumber = 1
            
            
            while (iterationNumber <= timesTwoDividNumber - 1) and (randomNumberWithPower != number - 1):
               
                randomNumberWithPower = pow(randomNumberWithPower, 2, number)
                
                
                iterationNumber = iterationNumber + 1
           
            if (randomNumberWithPower != (number - 1)):
                return False
            
    
    return True

T = int(raw_input())

lst = []
t = raw_input()
for i in range(T):
    lst.append(int(raw_input()))
for i in range(T):
    r = Prime_Test(lst[i])
    if r == True:
        print "YES"
    else:
        print "NO"