#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <stdlib.h>#include <time.h>#define LL __int64using namespace std;LL ans;const LL C=201;LL random(LL n){	return (LL)((double)rand()/RAND_MAX*n+0.5);}LL gcd(LL a,LL b){	if(b==0) return a;	return gcd(b,a%b);}LL multi(LL a,LL b,LL m){  a*b%m这个函数写得真心好，很好地避免了超出范围的情    况	LL ret=0;	while(b>0){		if(b&1)		ret=(ret+a)%m;		b>>=1;		a=(a<<1)%m;	}	return ret;}LL Pollard_rho(LL n, LL c){	LL x,y,d,i=1,k=2;	x=random(n-1)+1;	y=x;	while(true){		i++;		x=(multi(x,x,n)+c)%n;		d=gcd(y-x,n);		if(d>1&&d<n) return d;		if(y==x) return n;		if(i==k){			y=x;			k=k<<1;		}	}}LL quick(LL a,LL k,LL m){	LL ans=1;	a%=m;	while(k){		if(k&1){			ans=multi(ans,a,m);		}		k=k>>1;		a=multi(a,a,m);   // 这里如果不写函数直接乘会超范围	}	return ans;}bool Witness(LL a, LL n){	LL m=n-1;	int j=0;	while(!(m&1)){		j++;		m=m>>1;	}	LL x= quick(a,m,n);	if(x==1||x==n-1)	return false;	while(j--){		x=multi(x,x,n);		if(x==n-1)		return false;	}	return true;}bool Miller_Rabin(LL n){	if(n<2) return false;	if(n==2) return true;	if(!(n&1)) return false;	for(int i=1;i<=10;i++){		LL a=random(n-2)+1;		if(Witness(a,n)) return false;	}	return true;}void find(LL n){	if(n==1) return ;	if(Miller_Rabin(n)){		if(n<ans)		ans=n;		return ;	}	LL p=n;	while(p>=n)	p=Pollard_rho(p,random(n-2)+1);	find(p);	find(n/p);}int main(){	LL n; int T;	srand(time(0));	scanf("%d",&T);	while(T--){		scanf("%I64d",&n);		if(Miller_Rabin(n)){			printf("Prime\n");			continue;		}		ans=(1LL<<60);		find(n);		printf("%I64d\n",ans);	}	return 0;}