# your code goes here
def is_prime(x):
if x == 1:
return False
i = 2
while i*i <= x:
if x % i == 0:
return False
i += 1
return True
numtest = int(input())
count = 1
while count <= numtest:
f1 = int(input())
if is_prime(f1):
print("Prime")
else:
print("Not Prime")
count = count + 1
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBpc19wcmltZSh4KToKCWlmIHggPT0gMToKCQlyZXR1cm4gRmFsc2UKCWkgPSAyCgl3aGlsZSBpKmkgPD0geDoKCQlpZiB4ICUgaSA9PSAwOgoJCQlyZXR1cm4gRmFsc2UKCQlpICs9IDEKCXJldHVybiBUcnVlCiAKbnVtdGVzdCA9IGludChpbnB1dCgpKQpjb3VudCA9IDEKd2hpbGUgY291bnQgPD0gbnVtdGVzdDoKCWYxID0gaW50KGlucHV0KCkpCglpZiBpc19wcmltZShmMSk6CgkJcHJpbnQoIlByaW1lIikKCWVsc2U6CgkJcHJpbnQoIk5vdCBQcmltZSIpCgljb3VudCA9IGNvdW50ICsgMQ==