#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <time.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
ll random(ll n)
{
return ((double)rand()/RAND_MAX*n+0.5);
}
ll powmuilt(ll a,ll b,ll mod)
{
ll ans=0;
while(b)
{
if(b & 1)
{
ans = (ans+a)%mod;
}
b>>=1;
a= (2*a)%mod;
}
return ans;
}
ll powexp(ll a, ll b, ll mod)
{
ll ans=1;
while(b)
{
if(b & 1) ans = powmuilt(ans,a,mod);
b>>=1;
a = powmuilt(a,a,mod);
}
return ans;
}
bool wintness(ll a, ll n)
{
ll d=n-1;
while (!(d & 1)) d>>=1;
ll t=powexp(a,d,n);
while( d!=n-1 && t!=1 && t!=n-1)
{
t = powmuilt(t,t,n);
d<<=1;
}
return t==n-1|| d&1 ;
}
bool miller_rabin(ll n)
{
if(n==2) return 1;
if(n<2 || !(n&1)) return 0;
for(int i=1;i<=10;++i)
{
ll a=random(n-2)+1;
if(!wintness(a,n)) return 0;
}
return 1;
}
ll gcd(ll a ,ll b)
{
if(b==0) return a;
return gcd(b,a%b);
}
ll pollard_rho(ll n, ll c)
{
ll x,y,d,i=1,k=2;
x=random(n-2)+1;
y=x;
while(1)
{
++i;
x=(powmuilt(x,x,n)+c)%n;
d=gcd(y-x,n);
if(1<d &&d<n) return d;
if(x==y) return n;
if(i==k)
{
y=x; k<<=1;
}
}
}
ll mi;
void ffind(ll n,ll c)
{
if(n==1) return;
if(miller_rabin(n))
{
mi=min(mi,n);
return ;
}
ll p=n;
while(p>=n) p=pollard_rho(p,c--);
ffind(p,c);
ffind(n/p,c);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll n;
scanf("%lld",&n);
mi =n;
if(miller_rabin(n))
{
printf("Prime\n");
}
else
{
ffind(n,12312);
printf("%lld\n",mi);
}
}
return 0;
}
