you-just-went-full-retard-never-go-full-retard-1
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

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


import random
def Fermat(n):
	if n>1 :
		for times in range(5):
			randNum=random.randint(1,n-1)
			if pow(randNum,n-1,n)!=1 :
				return False
		return True
	return False
T=eval(input());
a=input()
for _ in range(T):
	N=eval(input());
	if Fermat(N):
		print("YES")
	else:
		print("NO")


t=eval(input())
assert(input()=="")
assert(t<=500)
while t:
	t-=1
	n=eval(input())
	i=2
	flag="YES"
	if (n==0 or n==1):
		flag="NO"
	while i*i<=n:
		if n%i==0:
			flag="NO"
			break
		i+=1
	print(flag)


def isprime(number):
	if number==1:
		return 0
	if number==2:
		return 1
	if number%2==0:
		return 0
	N=number**0.5
	i=3
	while i<=N:
		if number%i==0:
			return 0
		i=i+2
	return 1

def main():
	t=eval(input())
	s=input()
	while t:
		number=int(input())
		if isprime(number):
			print("YES")
		else:
			print("NO")
		t=t-1 
main()


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(input())

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