#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[15] = {2,3,5,7,11,13,17,19,23,29,31,37};
ll ans = -1;
ll gcd(ll a,ll b){
	return (b==0)?a:gcd(b,a%b);
}
ll times(ll a,ll b,ll p){
	ll ans = 0;
	while(b){
		if(b&1){
			ans += a;
			ans %= p;
		}
		a = (a+a)%p;
		b >>= 1;
	}
	return ans;
}
ll pow(ll a,ll b,ll p){
	ll ans = 1;
	while(b){
		if(b&1){
			ans = times(ans,a,p) %p;
		}
		a = times(a,a,p) %p;
		b >>= 1;
	}
	return ans%p;
}
bool check(ll n,ll pri){//判断是否为合数 
	ll d = n-1,r = 0;
	while(!(d&1)){
		d >>= 1;
		r ++;
	}
	ll x = pow(pri,d,n);
	if(x == 1){
		return true;
	}
	for(int i=0;i<r;i++){
		if(x == n-1){
			return true;
		}
		x = 1ll*x*x%n;
	}
	return false;
}
bool mr(ll t){//判断是否为质数 
	if(t<2){
		return false;
	}
	if(t <= 40ll){
		for(int i=0;i<=11;i++){
			if(prime[i] == t){
				return true;
			}
		}
	}else{
		for(int i=0;i<=11;i++){
			if(!check(t,prime[i])){
				return false;
			}
		}
	}
	return true;
}
ll f(ll a,ll n,ll c){
	return (times(a,a,n)+c)%n;
}
ll pr(ll n){
	ll c = rand()%(n-1ll)+1ll;
	ll v1 = c;
	ll v2 = f(v1,n,c);
	while(v1 != v2){
		int g = gcd(n,abs(v1-v2));
		if(g != 1ll){
			return g;
		}
		v1 = f(v1,n,c);
		v2 = f(v2,n,c);
		v2 = f(v2,n,c);
	}
	return n;
}
void fac(ll n){
	if(mr(n)){
		return;
	}
	ll a1 = pr(n);
	ll a2 = n/a1;
	if(mr(a1)){
		ans = max(ans,a1);
	}else{
		fac(a1);
	}
	if(mr(a2)){
		ans = max(ans,a2);
	}else{
		fac(a2);
	}
	return;
}
int main(){
	ll T,n;
	srand(time(0));
	scanf("%lld",&T);
	while(T--){
		ans = 0;
		scanf("%lld",&n);
		if(mr(n)){
			puts("Prime");
		}else{
			fac(n);
			printf("%lld\n",ans);
		}
	}
}