#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>using namespace std;__int64 pri[]= {2,3,5,7,11,13,17,19,23,29,31};//用小素数表做随机种子避免第一类卡米歇尔数的误判__int64 multi(__int64 a,__int64 b,__int64 n) //乘法快速幂{    __int64 tmp=0;    while(b)    {        if(b&1)        {            tmp+=a;            if(tmp>=n) tmp-=n;        }        a<<=1;        if(a>=n) a-=n;        b>>=1;    }    return tmp;}__int64 multimod(__int64 a,__int64 m,__int64 n) //乘法快速幂{    __int64 tmp=1;    a%=n;    while(m)    {        if(m&1) tmp=multi(tmp,a,n);        a=multi(a,a,n);        m>>=1;    }    return tmp;}__int64 gcd(__int64 a, __int64 b)        //迭代算法{    while(b)    {       __int64 c=a%b;       a=b;       b=c;    }    return a;}bool Miller_Rabin(__int64 n) //大素数判断{    if(n<2)        return false;    if(n==2)        return true;    if(!(n&1))        return false;    __int64 k=0,j,m,a;    m=n-1;    while(!(m&1))    {        m>>=1;        k++;    }    for(int i=0; i<10; i++)    {        if(pri[i]>=n)            return true;        a=multimod(pri[i],m,n);        if(a==1)            continue;        for(j=0; j<k; j++)        {            if(a==n-1)                break;            a=multi(a,a,n);        }        if(j==k)            return false;    }    return true;}__int64 pollard_rho(__int64 c,__int64 n) //查找因数{    __int64 i,x,y,k,d;    i=1;    x=y=rand()%n;    k=2;    do    {        i++;        d=gcd(n+y-x,n);        if(d>1 && d<n)            return d;        if(i==k)        {            y=x;            k<<=1;        }        x=(multi(x,x,n)+n-c)%n;    }    while(y!=x);    return n;}__int64 rho(__int64 n){    if(Miller_Rabin(n))        return n;    __int64 t=n;    while(t>=n)        t=pollard_rho(rand()%(n-1)+1,n);    __int64 a=rho(t);    __int64 b=rho(n/t);    return a<b? a:b;}__int64 ans[10000005],flag;void rhoAll(__int64 n) //计算全部质因子{    if(Miller_Rabin(n))    {        ans[flag++]=n;        return;    }    __int64 t=n;    while(t>=n)        t=pollard_rho(rand()%(n-1)+1,n);    rhoAll(t);    rhoAll(n/t);    return;}int main(){    //freopen("in.txt","r",stdin);    int t;    __int64 n;    scanf("%d",&t);    while(t--)    {        flag=0;        scanf("%I64d",&n);        if(Miller_Rabin(n))            printf("Prime\n");        else        {            //rhoAll(n);            printf("%I64d\n",rho(n));        }        /*for(int i=0;i<flag;i++) //输出全部质因子            if(i!=flag-1)                printf("%I64d ",ans[i]);            else                printf("%I64d\n",ans[i]);*/    }    return 0;}