from Crypto.Util.number import *
from random import *
A=0
def culc(x,c,n):
    return (x*x+c)%n
def PollardRho(x):
    s,t,goal,val=0,0,1,1
    c=getrandbits(64)%(x-1)+1
    while 1:
        for det in range(1,goal+1):
            t=culc(t,c,x)
            val=val*abs(t-s)%x
            if(det%127==0):
                d=GCD(val,x)
                if(d>1):
                    return d
        d=GCD(val,x)
        if(d>1):
            return d
        goal*=2
        s=t
        val=1
def factor(x):
    global A
    if(x<=A or x<2):
        return
    if(isPrime(x)):
        A=max(A,x)
        return
    p=x
    while(p>=x):
        p=PollardRho(x)
    while((x%p)==0):
        x//=p
    factor(x)
    factor(p)
T=int(input())
while T>0:
    T-=1
    A=0
    a=int(input())
    if(isPrime(a)):
        print('Prime')
    else:
        factor(a)
        print(A)