from math import*
def is_prime(x):
if x < 2:
return False;
for i in range(2,int(sqrt(x))+1):
if x%i==0:
return False
return True
n=int(input())
for i in range(n):
x=int(input())
if is_prime(x):
print("%d is prime"%(x))
else:
print("%d is not prime"%(x))