Miller-Rabin模板
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long T,n,mx;
long long mul(long long a,long long b,long long mod)
{
long long nw=a*b-(long long)((long double)a/mod*b+1e-8)*mod;
return nw<0?nw+mod:nw;
}
long long gcd(long long a,long long b)
{
return !b?a:gcd(b,a%b);
}
long long ksm(long long a,long long b,long long mod)
{
long long r=1;
a%=mod;
while(b)
{
if(b&1)
r=mul(r,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return r;
}
bool ok(long long a,long long n,long long r,long long s)
{
long long ans=ksm(a,r,n),p=ans;
for(int i=1;i<=s;i++)
{
ans=mul(ans,ans,n);
if(ans==1&&p!=1&&p!=n-1)
return 1;
p=ans;
}
return ans!=1;
}
bool mr(long long n)
{
if(n<=1)
return 0;
if(n==2)
return 1;
if(n%2==0)
return 0;
long long r=n-1,s=0;
while(r%2==0)
r/=2,s++;
for(int i=0;i<10;i++)
if(ok(rand()%(n-1)+1,n,r,s))
return 0;
return 1;
}
long long clc(long long n,long long c)
{
long long k=2,x=rand()%n,y=x,p=1;
for(int i=1;p==1;i++)
{
x=(mul(x,x,n)+c)%n;
p=gcd(n,abs(x-y));
if(i==k)
y=x,k*=2;
}
return p;
}
void wk(long long n)
{
if(n==1)
return;
if(mr(n))
{
mx=max(mx,n);
return;
}
long long x=n;
while(x==n)
x=clc(n,rand()%(n-1)+1);
wk(x);
wk(n/x);
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
mx=0;
wk(n);
if(mx==n)
puts("Prime");
else
printf("%lld\n",mx);
}
return 0;
}