from math import ceil, sqrt

def prime(x):
    if x == 2:
        return "Prime"
    elif x == 1 or (x & 1) == 0:
        return "Not prime"
    for i in range(2, ceil(sqrt(x)) + 1):
        if x % i == 0:
            return "Not prime"
    return "Prime"

print('\n'.join([prime(int(input())) for _ in range(int(input()))]))