#include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <bitset>

 #include <list>

 #include <cassert>

 #include <complex>

 using namespace std;

 #define rep(i,a,n) for (int i=a;i<n;i++)

 #define per(i,a,n) for (int i=n-1;i>=a;i--)

 #define all(x) (x).begin(),(x).end()

 //#define fi first

 #define se second

 #define SZ(x) ((int)(x).size())

 #define TWO(x) (1<<(x))

 #define TWOL(x) (1ll<<(x))

 #define clr(a) memset(a,0,sizeof(a))

 #define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long ll;

 typedef long double LD;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> PLL;

 typedef vector<ll> VL;

 typedef vector<PII> VPII;

 typedef complex<double> CD;

 const int inf=0x20202020;

 const ll mod=;

 const double eps=1e-;

 ll powmod(ll a,ll b)             //return (a*b)%mod

 {ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}

 ll powmod(ll a,ll b,ll mod)     //return (a*b)%mod

 {ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}

 ll gcd(ll a,ll b)                 //return gcd(a,b)

 { return b?gcd(b,a%b):a;}

 // head

 namespace Factor {

     const int N=;

     ll C,fac[],n,mut,a[];

     int T,cnt,i,l,prime[N],p[N],psize,_cnt;

     ll _e[],_pr[];

     vector<ll> d;

     inline ll mul(ll a,ll b,ll p) {     //return (a*b)%p

         if (p<=) return a*b%p;

         else if (p<=1000000000000ll) return (((a*(b>>)%p)<<)+(a*(b&((<<)-))))%p;

         else {

             ll d=(ll)floor(a*(long double)b/p+0.5);

             ll ret=(a*b-d*p)%p;

             if (ret<) ret+=p;

             return ret;

         }

     }

     void prime_table(){     //prime[1..tot]: prime[i]=ith prime

         int i,j,tot,t1;

         for (i=;i<=psize;i++) p[i]=i;

         for (i=,tot=;i<=psize;i++){

             if (p[i]==i) prime[++tot]=i;

             for (j=;j<=tot && (t1=prime[j]*i)<=psize;j++){

                 p[t1]=prime[j];

                 if (i%prime[j]==) break;

             }

         }

     }

     void init(int ps) {                 //initial

         psize=ps;

         prime_table();

     }

     ll powl(ll a,ll n,ll p) {           //return (a^n)%p

         ll ans=;

         for (;n;n>>=) {

             if (n&) ans=mul(ans,a,p);

             a=mul(a,a,p);

         }

         return ans;

     }

     bool witness(ll a,ll n) {

         int t=;

         ll u=n-;

         for (;~u&;u>>=) t++;

         ll x=powl(a,u,n),_x=;

         for (;t;t--) {

             _x=mul(x,x,n);

             if (_x== && x!= && x!=n-) return ;

             x=_x;

         }

         return _x!=;

     }

     bool miller(ll n) {

         if (n<) return ;

         if (n<=psize) return p[n]==n;

         if (~n&) return ;

         for (int j=;j<=;j++) if (witness(rand()%(n-)+,n)) return ;

         return ;

     }

     ll gcd(ll a,ll b) {

         ll ret=;

         while (a!=) {

             if ((~a&) && (~b&)) ret<<=,a>>=,b>>=;

             else if (~a&) a>>=; else if (~b&) b>>=;

             else {

                 if (a<b) swap(a,b);

                 a-=b;

             }

         }

         return ret*b;

     }

     ll rho(ll n) {

         for (;;) {

             ll X=rand()%n,Y,Z,T=,*lY=a,*lX=lY;

             int tmp=;

             C=rand()%+;

             X=mul(X,X,n)+C;*(lY++)=X;lX++;

             Y=mul(X,X,n)+C;*(lY++)=Y;

             for(;X!=Y;) {

                 ll t=X-Y+n;

                 Z=mul(T,t,n);

                 if(Z==) return gcd(T,n);

                 tmp--;

                 if (tmp==) {

                     tmp=;

                     Z=gcd(Z,n);

                     if (Z!= && Z!=n) return Z;

                 }

                 T=Z;

                 Y=*(lY++)=mul(Y,Y,n)+C;

                 Y=*(lY++)=mul(Y,Y,n)+C;

                 X=*(lX++);

             }

         }

     }

     void _factor(ll n) {

         for (int i=;i<cnt;i++) {

             if (n%fac[i]==) n/=fac[i],fac[cnt++]=fac[i];}

         if (n<=psize) {

             for (;n!=;n/=p[n]) fac[cnt++]=p[n];

             return;

         }

         if (miller(n)) fac[cnt++]=n;

         else {

             ll x=rho(n);

             _factor(x);_factor(n/x);

         }

     }

     void dfs(ll x,int dep) {

         if (dep==_cnt) d.push_back(x);

         else {

             dfs(x,dep+);

             for (int i=;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+);

         }

     }

     void norm() {

         sort(fac,fac+cnt);

         _cnt=;

         rep(i,,cnt) if (i==||fac[i]!=fac[i-]) _pr[_cnt]=fac[i],_e[_cnt++]=;

             else _e[_cnt-]++;

     }

     vector<ll> getd() {

         d.clear();

         dfs(,);

         return d;

     }

     vector<ll> factor(ll n) {       //return all factors of n        cnt:the number of factors

         cnt=;

         _factor(n);

         norm();

         return getd();

     }

     vector<PLL> factorG(ll n) {

         cnt=;

         _factor(n);

         norm();

         vector<PLL> d;

         rep(i,,_cnt) d.push_back(make_pair(_pr[i],_e[i]));

         return d;

     }

     bool is_primitive(ll a,ll p) {

         assert(miller(p));

         vector<PLL> D=factorG(p-);

         rep(i,,SZ(D)) if (powmod(a,(p-)/D[i].first,p)==) return ;

         return ;

     }

 }

 /* *************************************************

 * Miller_Rabin算法进行素数测试

 *速度快，可以判断一个  < 2^63的数是不是素数

 *

 **************************************************/

 const int S = ; //随机算法判定次数，一般8~10就够了

 //计算ret  = (a*b)%c

 long long mult_mod(long long a,long long b,long long  c)

 {

     a %= c;

     b %= c;

     long long ret = ;

     long long tmp = a;

     while(b)

     {

         if(b & )

         {

             ret += tmp;

             if(ret > c)ret -= c;//直接取模慢很多

         }

         tmp <<= ;

         if(tmp > c)tmp -= c;

         b >>= ;

     }

     return  ret;

 }

 //计算  ret = (a^n)%mod

 long long pow_mod(long long a,long long n,long long  mod)

 {

     long long ret = ;

     long long temp = a%mod;

     while(n)

     {

         if(n & )ret = mult_mod(ret,temp,mod);

         temp = mult_mod(temp,temp,mod);

         n >>= ;

     }

     return  ret;

 }

 //通过  a^(n-1)=1(mod n)来判断n是不是素数

 // n-1 = x*2^t中间使用二次判断

 //是合数返回true,不一定是合数返回false

 bool check(long long a,long long n,long long x,long long  t)

 {

     long long ret = pow_mod(a,x,n);

     long long last = ret;

     for(int i = ; i <= t; i++)

     {

         ret = mult_mod(ret,ret,n);

         if(ret ==  && last !=  && last != n-)return  true;//合数

         last = ret;

     }

     if(ret != )return true;

     else return false;

 }

 //**************************************************

 // Miller_Rabin算法

 //是素数返回true,(可能是伪素数)

 //不是素数返回false

 //**************************************************

 bool Miller_Rabin(long long  n)

 {

     if( n < )return false;

     if( n == )return true;

     if( (n&) == )return false;//偶数

     long long x = n - ;

     long long t = ;

     while( (x&)== )

     {

         x >>= ;

         t++;

     }

     rand();/* *************** */

     for(int i = ; i < S; i++)

     {

         long long a =  rand()%(n-) + ;

         if( check(a,n,x,t) )

             return false;

     }

     return true;

 }

 ll x,y,k,n;

 int _;

 int main() {

     Factor::init();

     cin>>_;

     while (_--)

     {

         cin>>n;

         bool ok=Miller_Rabin(n);

         if (n==)

         {

             cout<<<<endl;

             continue;

         }

         else if (n==)

         {

             cout<<"Prime"<<endl;

             continue;

         }

         if (ok) cout<<"Prime"<<endl;

         else

         {

             vector <PLL> p=Factor::factorG(n);

             //for (vector<ll>::iterator i=p.begin();i!=p.end();i++)

              //   cout<<*i<<" ";

              vector<PLL>::iterator i=p.begin();

             //printf("%d\n",*i);

             cout<<i->first<<endl;

         }

     }

 }