#include<bits/stdc++.h>
using namespace std;
#define rg register
#define RP(i,a,b) for(register int i=a;i<=b;++i)
#define DRP(i,a,b) for(register int i=a;i>=b;--i)
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
typedef long long ll;
typedef double db;
#define lll __int128
using namespace std;
int T;
ll ck[13]={2,3,5,7,11,13,17,19,23,29,31,37,61};
bool mul(ll a,ll p)
{
	ll b=p-1,ans=1;
	while(b)
	{
		if(b&1)
		{
			ans*=a;
			ans%=p;
		}
		a*=a;
		a%=p;
		b>>=1;
	}
	if(ans==1)
	{
		return true;
	}
	return false;
}
bool prime(ll x)
{
	if(x==1)
	{
		return false;
	}
	else if(x==2)
	{
		return true;
	}
	for(int i=0;i<13;++i)
	{
		if(!mul(ck[i],x)&&ck[i]!=x)
		{
			return false;
		}
	}
	return true; 
}
ll f(ll x,ll c,ll n)
{
	return ((lll)x*x+c)%n;
}
ll gcd(ll x,ll y)
{
	if(x%y)
	{
		return gcd(y,x%y);
	}
	return y;
}

ll Pollard_Rho(ll x)
{
     if(x==4)
	{
		return 2;
	}	
	if(prime(x))
    {
		return x;
	} 
	if(x==1)
	{
		return 1;
	}
	while(1)
	{
		ll c=1ll*rand()%(x-1)+1;
		ll t=0,r=0,p=1,q;
		//auto f = [=](ll x) { return ((lll)x * x + c) % N; };
		do{
		    for(int i=0;i<128;++i)
			{
				t=f(t,c,x),r=f(f(r,c,x),c,x);
				q=(lll)p*abs(t-r)%x;
				if(t==r||q==0)
				{
					break;
				}
				p=q;
			}
			ll d=gcd(p,x);
			if(d>1)
			{
				return d;
			}
		}while(t!=r);
	}
}
map<ll,ll> num;
ll max_prime(ll x)
{
	if(num[x])
	{
		return num[x];
	}
	ll ans=Pollard_Rho(x);
	if(ans==1||ans==x)
	{
		num[x]=x;
	} 
	else
	{
		num[x]=max(max_prime(ans),max_prime(x/ans));
	}
	return num[x];
}
int main()
{
	
	scanf("%d",&T);
	while(T--)
	{
		ll n;
		scanf("%lld",&n);
		if(max_prime(n)==n)
		{
			cout<<"Prime"<<endl;
			continue;
		}
		printf("%lld\n",max_prime(n));
	}
	return 0;
}