#include <iostream>

 #include <algorithm>

 #define ll long long

 using namespace std;

 const int MAXN = 1e2;

 const int repeat = ;//repeat为检测次数,判断错误率为4^-repeat,一般8~10就够了

 ll get_mult(ll a, ll b, ll c){//返回a*b%c

     a %= c;

     b %= c;

     ll ret = ;

     while(b){

         if(b & ){

             ret += a;

             if(ret >= c) ret -= c;

         }

         b >>= ;

         a <<= ;

         if(a >= c) a -= c;

     }

     return ret;

 }

 ll get_pow(ll x, ll n, ll mod){//返回x^n%mod

     ll ret = ;

     x %= mod;

     while(n){

         if(n & ) ret = get_mult(ret, x, mod);

         x = get_mult(x, x, mod);

         n >>= ;

     }

     return ret;

 }

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

 //n-1 = x*2^t 中间使用二次探测定理

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

 bool cherk(ll a, ll n, ll x, ll t){

     ll ret = get_pow(a, x, n);

     ll last = ret;

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

         ret = get_mult(ret, ret, n);

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

         last = ret;

     }

     if(ret != ) return true;

     return false;

 }

 bool Miller_Rabin(ll n){

     if(n < ) return false;

     if(n == ) return true;

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

     ll x = n - , t = ;

     while(!(x & )){

         x >>= ;

         t++;

     }

     // srand(time(NULL));

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

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

         if(cherk(a, n, x, t)) return false;

     }

     return true;

 }

 ll factor[MAXN];

 int tot;//n的质因子个数

 ll get_gcd(ll a, ll b){

     ll tmp;

     while(b){

         tmp = a;

         a = b;

         b = tmp % b;

     }

     return a >=  ? a : -a;

 }

 ll pollard_rho(ll x, ll c){//返回x的一个因子

     ll i = , k = ;

     // srand(time(NULL));

     ll x0 = rand() % (x - ) + ;

     ll y = x0;

     while(){

         i++;

         x0 = (get_mult(x0, x0, x) + c) % x;

         ll d = get_gcd(y - x0, x);

         if(d !=  && d != x) return d;

         if(y == x0) return x;

         if(i == k){

             y = x0;

             k += k;

         }

     }

 }

 void findfac(ll n, int k){//对n质因分解并将结果保存到factor中

     if(n == ) return;

     if(Miller_Rabin(n)){

         factor[tot++] = n;

         return;

     }

     ll p = n;

     int c = k;//c防止死循环

     while(p >= n){

         p = pollard_rho(p, c--);

     }

     findfac(p, k);

     findfac(n / p, k);

 }

 int main(void){

     ll n;

     int t;

     cin >> t;

     while(t--){

         cin >> n;

         if(Miller_Rabin(n)) cout << "Prime" << endl;

         else{

             tot = ;

             findfac(n, );

             ll sol = factor[];

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

                 sol = min(sol, factor[i]);

             }

             cout << sol << endl;

         }

     }

     return ;

 }