RT.

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
extern "C" {
	namespace io {
#define BUFS 100000
		static char in[BUFS], *p = in, *pp = in;
#define gc (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
		inline ll read() {
			reg ll x = 0; reg char ch, f = 0;
			while (!isdigit(ch = gc)) f |= ch == '-';
			while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc;
			return f ? -x : x; 
		}
	}
}
#define rd io :: read
const int MAX = 1000000, MAXP = 80000;
int pn = 0, c[MAX], p[MAXP];
ll mxfac;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
inline void sieve() {
	for (reg int i = 2; i < MAX; ++i) {
		c[i] || (p[++pn] = i);
		for (reg int j = 1, v; j <= pn && (v = i * p[j]) < MAX; ++j)
			(c[v] = p[j], i % p[j]) || (j = pn);
	}
}
inline ll multi(ll a, ll b, ll p) {
	ll tmp = (a * b - (ll)((long double)a * b / p) * p) % p;
	return tmp + (tmp >> 63 & p);
}
inline ll qpow(ll a, ll b, ll p) {
	reg ll res = 1;
	for (; b; b >>= 1, a = multi(a, a, p)) (b & 1) && (res = multi(res, a, p), false);
	return res;
}
const int test[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
inline bool MR(ll n) {
	if (n < MAX) return n > 1 && !c[n];
	ll s = n - 1, u, v, lg;
	for (lg = 0; !(s & 1); ++lg, s >>= 1);
	for (reg int i = 0; i < 7; ++i) {
		if (n % test[i] == 0) return false;
		u = qpow(test[i], s, n);
		for (reg int j = 0; j < lg; ++j, u = v)
			if (v = multi(u, u, n), u != 1 && u != n - 1 && v == 1) return false;
		if (u != 1) return false;
	}
	return true;
}
inline ll rnd(ll x, ll c, ll mod) {
	return (multi(x, x, mod) + c) % mod;
}
ll PR(ll n, ll c) {
	ll x = rand() % (n - 1) + 1, y = x, p;
	for (reg int i = 1, k = 2; k <= 131072; ) {
		x = rnd(x, c, n);
		p = gcd(abs(x - y), n);
		if (p != 1 && p != n) return p;
		if (++i == k) y = x, k <<= 1;
	}
	return 0;
}
void fac(ll n) {
	if (n <= mxfac || n < 2) return ;
	if (MR(n)) {mxfac = max(mxfac, n); return ;}
	ll p;
	if (n < MAX) p = c[n];
	if (n >= MAX) for (reg int k = 97; !(p = PR(n, k)); --k);
	fac(p);
	while (n % p == 0) n /= p;
	fac(n);
}
ll calc(ll n) {
	mxfac = 0;
	return fac(n), mxfac;
}
int main() {
	srand(time(0));
	sieve();
	for (reg int T = rd(); T; --T) {
		ll n = rd(), ans = calc(n);
		if (ans == n) puts("Prime");
		else printf("%lld\n", ans);
	}
	return 0;
}