已经把龟速乘换成__int128了，还是会炸。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib> 
#include<cmath>
using namespace std; 
#define int __int128
#define ri register int
#define rd(n) n=read()
inline int read(void)
{
	register int res=0,f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){f^=(c=='-');c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
	return f?-res:res;
}
inline void fprint(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9) fprint(n/10);
	putchar(n%10+'0');
}
inline void print(int n)
{
	fprint(n);
	putchar('\n');
} 
int t,n,m,k,x,y,z,ans,res,prime[1000005];
bool v[1000005];
inline void Eratosthenes(int n)
{
	v[1]=1;
	for(ri i=2;i<=n;++i)
	{
		if(v[i]) continue;
		prime[++m]=i;
		for(ri j=i*i*1ll;j<=n;j+=i) v[j]=1;
	}
} 
inline int mul(int a,int b,int p)
{
	ri ret=0;
	for(;b;b>>=1)
	{
		if(b&1) ret=(ret%p+a%p)%p;
		a=(a%p+a%p)%p;
	}
	return ret%p;
}
inline int power(int a,int b,int p)
{
	ri ret=1%p;
	for(;b;b>>=1)
	{
		if(b&1) ret=(ret*a)%p;
		a=(a*a)%p;
	}
	return ret%p;
}
inline bool witness(int a,int n)
{
	ri u=n-1,t=0;
	t=__builtin_ctz(u);
	u>>=t;
	//while(!(u&1)){++t;u>>=1;}
	//cout<<t<<" "<<u<<" "<<(u&1)<<"\n";
	ri x=power(a,u,n),y=0;
	for(ri i=1;i<=t;++i)
	{
		y=(x*x)%n;
		if(y==1&&x!=1&&x!=n-1) return 0;
		x=y;
	}
	if(x!=1) return 0;
	return 1;
}
inline bool Miller_Rabin(int n)
{
	if(n<=1000000) return !v[n];
	if(n%2==0) return 0;
	for(ri i=1;i<=12;++i)
		if(!witness(prime[i],n)) return 0;
	return 1;
}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int Pollard_Rho(int n)
{
	if(n==4) return 2;
	ri x=rand()%n,y=x;
	ri c=rand()%(n-1)+1;
	ri k=2;
	for(ri i=1;i;++i)
	{
		ri x=(x*x)%n;
		x=(x+c)%n;
		ri d=gcd(y>x?y-x:x-y,n);
		if(d!=1&&d!=n) return d;
		if(y==x) return n;
		if(i==k) 
		{
			y=x;
			k<<=1ll; 
		}
	}
}
int fac=0;
inline void Divide(int n)
{ 
	if(Miller_Rabin(n)) 
	{
		fac=max(fac,n);
		return;
	}
	ri p=n;
	while(p>=n) p=Pollard_Rho(p);
	Divide(p);
	Divide(n/p);
}
signed main(void)
{  
	srand(19260817);
	Eratosthenes(1000000);
	rd(t);
	while(t--)
	{
		rd(n); fac=0;
		if(Miller_Rabin(n)) puts("Prime");
		else 
		{
			Divide(n);
			print(fac);
		}
	}
 	return 0;
}

/*
2
2152302898747
3215031751
*/