#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010, inf = 1e7;
mt19937 rnd(time(0));
int res;
int pr[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int quick_power(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1) res = (__int128)a * res % p;
a = (__int128)a * a % p;
b >>= 1;
}
return res;
}
bool MR(int p)
{
for (int i = 1; i <= 12; i ++ )
if (p == pr[i]) return true;
if (p < 40) return false;
int x;
for (int i = 1; i <= 12; i ++ )
{
x = pr[i];
if (quick_power(x, p - 1, p) != 1) return false;
int r = p - 1;
while (r % 2 == 0)
{
r >>= 1;
int qp = quick_power(x, r, p);
if (qp == p - 1) return true;
else if (qp != 1) return false;
}
}
return true;
}
int PR(int x)
{
if (MR(x)) return x;
if (x == 4) return 2;
while (true)
{
int c = rnd() % (x - 1) + 1;
// cerr << c << '\n';
auto f = [=](int n) { return ((__int128)n * n + c) % x; };
int a = f(0), b = f(a), p = 1, q;
for (int lim = 1; lim < 256 && a != b; lim <<= 1)
{
for (int i = 0; i < lim; i ++ )
{
if (a == b) break;
q = p * abs(a - b) % x;
if (!q) break;
p = q;
a = f(a), b = f(f(b));
}
int d = __gcd(x, p);
if (d > 1) return d;
}
}
}
void F(int x)
{
if (x <= res || x < 2) return;
if (MR(x))
{
res = max(res, x);
return;
}
int p = x;
while (p >= x) p = PR(x);
while (x % p == 0) x /= p;
F(x), F(p);
}
signed main()
{
int T;
cin >> T;
while (T -- )
{
int n;
cin >> n;
res = 0;
if (MR(n)) cout << "Prime\n";
else F(n), cout << res << '\n';
}
return 0;
}