hr.py

class D(dict):
    def __missing__(self, key):
        return True
d = D()


lim = 3000000
nums = xrange(2, lim)
for a in nums:
    if d[a]:
        for b in range(a*2, lim, a):
            d[b] = False

p = int(raw_input())
for _ in xrange(p):
    n = int(raw_input().strip())
    if d[n]:
        print "Prime"
    else:
        print "Not Prime"