#include <cstdio>

#include<time.h>

#include <algorithm>

#include<set>

using namespace std;

typedef long long llt;

int const Repeat = ;

set<llt>sss;

//利用二进制计算a*b%mod

llt multiMod(llt a, llt b, llt mod){

    llt ret = 0LL;

    a %= mod;

    while (b){

        if (b & 1LL) ret = (ret + a) % mod, --b;

        b >>= 1LL;

        a = (a + a) % mod;

    }

    return ret;

}

//计算a^b%mod

llt powerMod(llt a, llt b, llt mod){

    llt ret = 1LL;

    a %= mod;

    while (b){

        if (b & 1LL) ret = multiMod(ret, a, mod), --b;

        b >>= 1LL;

        a = multiMod(a, a, mod);

    }

    return ret;

}

//Miller-Rabin测试,测试n是否为素数

bool Miller_Rabin(llt n, int repeat){

    if (2LL == n || 3LL == n) return true;

    if (!(n & 1LL)) return false;

    //将n分解为2^s*d

    llt d = n - 1LL;

    int s = ;

    while (!(d & 1LL)) ++s, d >>= 1LL;

    //srand((unsigned)time(0));

    for (int i = ; i<repeat; ++i){//重复repeat次

        llt a = rand() % (n - ) + ;//取一个随机数,[2,n-1)

        llt x = powerMod(a, d, n);

        llt y = 0LL;

        for (int j = ; j<s; ++j){

            y = multiMod(x, x, n);

            if (1LL == y && 1LL != x && n - 1LL != x) return false;

            x = y;

        }

        if (1LL != y) return false;

    }

    return true;

}

llt Fac[];//质因数分解结果（刚返回时是无序的）

int FCnt;//质因数的个数。数组小标从0开始

llt gcd(llt a, llt b){

    if (0L == a || 0L == b) return ;

    if (a < ) a = -a;

    if (b < ) b = -b;

    while (b){

        llt t = a % b;

        a = b;

        b = t;

    }

    return a;

}

llt Pollard_Rho(llt n, llt c){

    llt i = , k = ;

    llt x = rand() % n;

    llt y = x;

    while (){

        ++i;

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

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

        if (d != 1LL && d != n) return d;

        if (y == x) return n;

        if (i == k) y = x, k <<= ;

    }

}

void find(llt n){

    if (4LL == n){

        Fac[] = Fac[] = 2LL;

        FCnt = ;

        return;

    }

    if (Miller_Rabin(n, Repeat)){

        Fac[FCnt++] = n;

        return;

    }

    llt p;

    while ((p = Pollard_Rho(n, rand() % (n - ) + )) == n);

    find(p);

    find(n / p);

}

int main(){

    int kase;

    scanf("%d", &kase);

    while (kase--){

        llt n;

        scanf("%lld", &n);

        FCnt = ;

        if (Miller_Rabin(n, )){ printf("Prime\n"); }

        else{

            find(n);

            llt ans = Fac[];

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

            if (ans>Fac[i])ans = Fac[i];

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

        }

    }

    return ;

}