WA 在了 #1、#9 上，好像是明明不是素数，然后输出 "Prime" ，但是我的 mr 是可以通过 SP288 的啊

// Problem: P4718 【模板】Pollard-Rho算法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4718
// Memory Limit: 125 MB
// Time Limit: 2000 ms
#include<stdio.h>
#include<random>
typedef unsigned long long ll;
inline ll sum(ll x,ll y,ll p){return (p-x)>y?x+y:y-(p-x);}
inline ll mult(ll x,ll y,ll p){return (__int128_t)x*y%p;}
inline ll pow(ll x,ll y,ll p){ll ans=1;for(;y;y>>=1){if(y&1)ans=mult(ans,x,p);x=mult(x,x,p);}return ans;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
inline ll myrand(){
	static std::random_device seed;
	static std::mt19937_64 rd(seed());
	return rd();
}
namespace miller_rabin{
	inline bool mr(ll a,ll n){
		ll m=n-1,k=0;for(;(m&1)==0;m>>=1)++k;
		ll cur=pow(a,m,n);if(cur==1||cur==n-1)return 1;
		for(;k&&(cur=mult(cur,cur,n));--k)if(cur==1||cur==n-1)return 1;
		return 0;
	}
	inline bool mr(ll n){
		if(n==1)return 0;
		static const ll a[]={2,3,5,13,17,31,37};
		for(const auto&i:a)if(n==i)return 1;
		for(const auto&i:a)if(!mr(i,n))return 0;
		return 1;
	}
}
using miller_rabin::mr;
namespace pollard_rho{
	inline ll f(ll s,ll c,ll n){return sum(mult(s,s,n),c,n);}
	inline ll pr(ll n){
		int cnt=0,k=1;ll x=myrand()%n,y=x,d,p=1,c=myrand()%(n-1)+1;
		for(;;){
			y=f(y,c,n),p=mult(p,(x>y?x-y:y-x),n);
			if(x==y)return n;
			if(++cnt==k){if((d=gcd(p,n))>1)return d;x=y,k<<=1;}
		}
	}
}
using pollard_rho::pr;
ll factor;
void fact(ll n){
	if(n<2||n<=factor)return;
	if(mr(n))return (void)(factor=n);
	ll d=n;while((d=(pr(n)))==n);
	while(!(n%d))n/=d;
	fact(d),fact(n);
}
int main(){
	int t;ll n;scanf("%d",&t);
	for(;t;--t){scanf("%llu",&n);factor=1;fact(n);if(factor==n)puts("Prime");else printf("%llu\n",factor);fflush(stdout);}
	return 0;
}