/*

 宋代谢逸

 《踏莎行·柳絮风轻》

 柳絮风轻，梨花雨细。春阴院落帘垂地。碧溪影里小桥横，青帘市上孤烟起。

 镜约关情，琴心破睡。轻寒漠漠侵鸳被。酒醒霞散脸边红，梦回山蹙眉间翠。

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <string>

 #include <ctime>

 #define LOCAL

 const int MAXN =  + ;

 using namespace std;

 typedef long long ll;

 ll n, Ans;

 //快速乘

 long long multi(long long a, long long b, long long c){

     if (b == ) return ;

     if (b == ) return a % c;

     long long tmp = multi(a, b / , c);

     if (b %  == ) return (tmp + tmp) % c;

     else return (((tmp + tmp) % c) + a) % c;

 }

 ll pow(ll a, ll b, ll p){

     if (b == ) return a % p;

     ll tmp = pow(a, b / , p);

     if (b %  == ) return (multi(tmp, tmp, p));

     else return multi(multi(tmp, tmp, p), (a % p), p);

 }

 //二次探测

 bool Sec_Check(ll a, ll p, ll c){

     ll tmp = pow(a, p, c);

     if (tmp !=  && tmp != (c - )) return ;//不通过

     if (tmp == (c - ) || (p %  != )) return ;

     return Sec_Check(a, p / , c);

 }

 bool miller_rabin(ll n){

     ll cnt = ;

     while (cnt--){

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

         if (!Sec_Check(a, n - , n)) return ;

     }

     return ;

 }

 //int f(int ) {return }

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

 long long BIGRAND() {return rand() * RAND_MAX + rand();}

 long long pollard_rho(long long n, long long c){

     long long x, y, d;

     long long i = , k = ;

      x = ((double)rand()/RAND_MAX*(n - )+0.5) + ;

     y = x;

     while(){

         i++;

           //注意顺序

         x = (multi(x, x, n) % n + c) % n;

         d = gcd(y - x + n, n);

         if( < d && d < n) return d;

         if(y == x) return n;

         if(i == k){

             y = x;

             k <<= ;

         }

     }

 }

 //

 void find(long long n, long long c){

     if (n == ) return;

     if (miller_rabin(n)) {

         if (Ans == -) Ans = n;

         else Ans = min(Ans, n);

         return ;

     }

     long long p = n;

     while (p >= n) p = pollard_rho(n, c--);

     find(p, c);

     find(n / p, c);

     //return find(p, c) + find(n / p, c);

 }

 int main(){

     int T;

     srand(time());

     scanf("%d", &T);

     while (T--){

         scanf("%lld", &n);

         if (n !=  && miller_rabin(n)) printf("Prime\n");

         else {

             Ans = -;

             find(n, );

             printf("%lld\n", Ans);

         }

     }

     return ;

 }