只有第十二个点过了。马蜂较优.

其中 Pollard-Rho 的判素用了费马小定理，已倍增优化、开__int128。

Q:分解函数 fac 中未剪枝不知道行不行

#include<bits/stdc++.h> 
using namespace std;
using ll = __int128;

// Start  ***************************
ll ffpow(ll a,ll base,ll mod) { 
	ll res=1,x=a;
	while(base) {
		if(base&1) res=res*x%mod;
		base>>=1,x=x*x%mod;
	}
	return res;
}
inline bool fer(ll a,ll b) {
	return a%b==0||(a+1)%b==0||(a-1)%b==0||ffpow(a,b-1,b)==1;
}
bool check(ll x) {
	if(x<2) return 0;
	if(!(x&1)) return x==2;
	return fer(2,x)&&fer(3,x)&&fer(5,x)&&fer(7,x)&&fer(11,x)&&fer(13,x)
		&&fer(17,x)&&fer(19,x)&&fer(23,x)&&fer(29,x)&&fer(31,x)&&fer(37,x);
}
// End ************************

ll gcd(ll aa,ll bb)
{
	if(bb==0) return aa;
	return gcd(bb,aa%bb);
}
long long n;
long long T;
inline ll f(ll pos,ll now,ll c){ // Next Step  
	return (pos*pos+c)%(now-1)+1;
}
ll rho(ll a)
{
	ll c=1ll*rand()%(a-1)+1;
	ll u=0,v=0,d;
	ll val=1;
	for(int len=1;   ;len<<=1,u=v,val=1){
		for(int i=0;i<=len;i++){
			v=f(v,a,c);
			val=val*((u>v)?u-v:v-u)%a;
			if(val==0) return a;
			if((i%127)==0) {
				d=gcd(((u>v)?u-v:v-u),a);
				if(d>1) return d;
			}
		}
		d=gcd(((u>v)?u-v:v-u),a);
		if(d>1) return d;
	}
	return a;
}
long long mx=0;
void fac(ll x)
{
	if(x<2||x<=mx) return;
	if(check(x)) {
		mx=max(mx,(long long)x);
		return;
	}
	ll p=x;
	while(p>=x) p=rho(x);
	while((x%p)==0) x/=p;
	fac(x),fac(p);
}
void MyWork()
{
	cin>>n;
	mx=0;
	if(check(n)) {
		puts("Prime");
		return;
	}
	fac(n);
	printf("%d\n",mx);
}
int main() {
	srand((__int128)time(NULL));
	cin>>T;while(T--) MyWork();
	return 0;
}