#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,num,q,tmp,ans;
inline __int128 mul(__int128 x,__int128 y) {
    return x*y;
}
inline int fastpow(int x,int t,int n) {
	int base=x,res=1;
	while (t) {
		if (t&1) res=mul(res,base)%n;
		base=mul(base,base)%n;
		t>>=1;
	}
	return res;
}
inline bool check(int n,int rd) {
	if (n%2==0) return false;
	int x=fastpow(rd,tmp,n)%n;
	if (x==1) return true;
	for (int i=0;i<num;i++) {
		if (x==n-1) return true;
		x=mul(x,x)%n;
	}
	return false;
}
inline bool Miller_Robin(int n) {
	if (n==2) return true;
	int t=10;
	tmp=n-1,num=0;
	bool flag=true;
	while (tmp%2==0) {
		tmp>>=1;
		num++;
	}
	while (t--) {
		int rd=rand()%(n-2)+2;
		if (!check(n,rd)) {
			flag=false;
			break;
		}
	}
	return flag;
}
inline int f(int x,int c,int n) {
	return (mul(x,x)%n+c)%n;
}
inline int getFactor(int n) {
	int s=0,t=0,c=rand()%(n-1)+1;
	int step,goal,val=1;
	for (goal=1;;goal<<=1,val=1,s=t) {
		for (step=1;step<=goal;++step) {
			t=f(t,c,n);
			val=mul(val,abs(t-s))%n;
			if (step%127==0) {
				int d=__gcd(val,n);
				if (d>1) return d;
			}
	    int d=__gcd(val,n);
	    if (d>1) return d;
	    }
	}
}
inline void Pollard_rho(int x) {
	if (x<=ans || x==1) return ;
	if (Miller_Robin(x)) {
	    ans=max(ans,x);
	    return ;
	}
	int p=x;
	while (p==x) p=getFactor(x);
	while (x%p==0) x/=p;
	Pollard_rho(p),Pollard_rho(x);
}
signed main() {
	int n;
	srand(time(0));
	scanf("%lld",&T);
	while (T--) {
		scanf("%lld",&n);
		if (n==2) {
			printf("Prime\n");
			continue;
		}
		if (Miller_Robin(n)) {
			printf("Prime\n");
			continue;
		}
		ans=0;
		Pollard_rho(n);
		printf("%lld\n",ans);
	}
	return 0;
}