import math

def is_prime(n: int) -> str:
    if n == 1:
        return "Not prime"
    ans = (
        next(
            filter(
                lambda x: n % x == 0,
                (div for div in range(2, math.floor(math.sqrt(n) + 1)))
            ), None
        )
    )
    return "Prime" if ans is None else "Not prime"
    
tests = [int(input()) for i in range(int(input()))]
for test in tests:
    print(is_prime(test))