#include "cstdio"
#include "cstdlib"
#include "algorithm"
#include "ctime"
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b) {
return b == 0 ? a : gcd(b,a % b);
}
LL muli_mod(LL n,LL k,LL p) {
LL m = 0;
while (k) {
if (k & 1) m = (m + n) % p;
n = (n + n) % p;
k >>= 1;
}
return m;
}
LL pow_mod(LL n,LL p) {
LL m = 1;
while (k) {
if (k & 1) m = muli_mod(m,n,p);
n = muli_mod(n,p);
k >>= 1;
}
return m;
}
LL miller_rabin(LL n) {
if (n == 2) return true;
if (n < 2 || !(n & 1)) return false;
LL m = n - 1; int s = 0;
while (!(m & 1)) s++,m >>= 1;
for (int i = 1; i <= 5; i++) {
LL r = rand() % (n - 1) + 1;
LL y = pow_mod(r,m,n);
for (int j = 1; j <= s; j++) {
LL x = muli_mod(y,y,n);
if (x == 1 && y != 1 && y != n - 1) return false;
y = x;
}
if (y != 1) return false;
}
return true;
}
LL pollard_rho(LL n,LL c) {
int i = 1,k = 2;
LL x = rand() % (n - 1) + 1;
LL y = x;
while (true) {
x = (muli_mod(x,x,n) + c) % n;
LL p = gcd((y - x + n) % n,n);
if (p > 1 && p < n) return p;
if (x == y) return n;
if (++i == k) {
k <<= 1;
y = x;
}
}
}
LL find(LL n) {
if (miller_rabin(n)) return n;
LL p = n;
while (p >= n) p = pollard_rho(p,rand() % (n - 1) + 1);
return min(find(p),find(n / p));
}
int main() {
int t; LL n;
// srand(time(NULL));
scanf("%d",&t);
while (t--) {
scanf("%lld",&n);
LL p = find(n);
if (p == n) puts("Prime");
else printf("%lldn",p);
}
return 0;
}