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