RT.

第 $13$ 个点 TLE。

#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef __int128 ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline ll read(){
   	ll x=0;bool sgn=0;char ch=gt();
   	while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
   	while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
	return sgn?-x:x;
}
template<class T>
inline void print(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
	static char st[70];short top=0;
	if(x<0)pt('-');
    do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
int T;
ll n,max_fac;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
inline ll ksm(ll a,ll b,ll mod){
	ll res=1;
	a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod,b>>=1;
	}
	return res;
}
inline ll mul(ll a,ll b,ll mod){
	ll res=0;
	a%=mod,b%=mod;
	while(b){
		if(b&1)res=(res+a)%mod;
		a<<=1;
		if(a>=mod)a-=mod;
		b>>=1;
	}
	return res;
}
namespace Miller_Rabin{
	const int prime[12]={2,3,5,7,11,13,17,19,23,29,31,37};
	const int pcnt=12;
	mt19937 Rand(time(0));
	inline bool witness(ll a,ll n){
		// =0 合数； =1 质数 
		ll u=n-1;
		int t=0;
		while(u%2==0) u>>=1,t++;
		ll x1=ksm(a,u,n),x2;
		for(int i=1;i<=t;++i){
			x2=(x1*x1)%n;
			if(x2==1&&x1!=1&&x1!=n-1)return 0;
			x1=x2;
		}
		return x1==1;
	}
	inline bool is_prime(ll n){
		// 对 n 进行 test_cnt 次测试，返回值 =0 合数，=1 质数 
		if(n<2)return 0;
		for(int i=0;i<pcnt;++i){
			if(n==prime[i])return 1;
			if(n%prime[i]==0)return 0;
			if(!witness((ll)prime[i]%n,n))return 0;
		}
		return 1;
	}
}
namespace Pollard_Rho{
	mt19937 Rand(time(0));
	inline ll pollard_rho(ll n){
		ll i=1,k=2;// i 为循环次数，k 为 2 的幂 
		ll c=Rand()%(n-1)+1;
		ll x=Rand()%n,y=x;
		while(1){
			i++;
			x=(mul(x,x,n)+c)%n;
			ll d=gcd((x>y)?(x-y):(y-x),n);
			if(d!=1&&d!=n)return d;
			if(y==x)return n;
			if(i==k)y=x,k<<=1;
		}
	}
	void findfac(ll n){
		if(n<2||max_fac>=n)return;
		if(Miller_Rabin::is_prime(n)){
			max_fac=max(max_fac,n);
			return;
		}
		ll p=n;
		while(p>=n) p=pollard_rho(p);
		while(n%p==0) n/=p;
		findfac(n),findfac(p);
	}
}
signed main(){
	T=read();
	while(T--){
		n=read(),max_fac=0;
		if(Miller_Rabin::is_prime(n)){
			printf("Prime\n");
		}else{
			Pollard_Rho::findfac(n);
			println(max_fac);
		}
	}
	return 0;
}