寄录

#include <iostream>
#include <chrono>
#include <numeric>
#include <random>
using namespace std;
using namespace chrono;
using ll = long long;
mt19937_64 mt_rand(duration_cast<nanoseconds>(system_clock::now().time_since_epoch()).count());
ll ans;
ll mult_mod(ll a, ll b, ll n)
{
    a %= n;
    b %= n;
    ll ret = 0;
    while (b) {
        if (b & 1) {
            ret += a;
            if (ret >= n)
                ret -= n;
        }
        a <<= 1;
        if (a >= n)
            a -= n;
        b >>= 1;
    }
    return ret;
}
ll fast_pow(ll x, ll y, ll m)
{
    ll res = 1;
    x %= m;
    while (y) {
        if (y & 1)
            res = mult_mod(res, x, m);
        x = mult_mod(x, x, m);
        y >>= 1;
    }
    return res;
}
bool witness(ll a, ll n)
{
    ll u = n - 1;
    int t = 0;
    while (!(u & 1)) {
        u >>= 1;
        ++t;
    }
    ll x1, x2;
    x1 = fast_pow(a, u, n);
    for (int i = 1; i <= t; i++) {
        x2 = fast_pow(x1, 2, n);
        if (x2 == 1 && x1 != 1 && x1 != n - 1)
            return true;
        x1 = x2;
    }
    if (x1 != 1)
        return true;
    return false;
}
int miller_rabin(ll n, int s = 50)
{
    if (n < 2)
        return 0;
    if (n == 2)
        return 1;
    if (n % 2 == 0)
        return 0;
    for (int i = 0; i < s && i < n; i++) {
        ll a = mt_rand() % (n - 1) + 1;
        if (witness(a, n))
            return 0;
    }
    return 1;
}
ll pollard_rho(ll n)
{
    ll i = 1, k = 2;
    ll c = mt_rand() % (n - 1) + 1;
    ll x = mt_rand() % n;
    ll y = x;
    while (true) {
        i++;
        x = (mult_mod(x, x, n) + c) % n;
        ll d = gcd(y > x ? y - x : x - y, n);
        if (d != 1 && d != n)
            return d;
        if (y == x)
            return n;
        if (i == k) {
            y = x;
            k = k << 1;
        }
    }
}
void findfac(ll n)
{
    if (miller_rabin(n)) {
        ans = max(ans, n);
        return;
    }
    ll p = n;
    while (p >= n)
        p = pollard_rho(p);
    findfac(p);
    findfac(n / p);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ans = 0;
        findfac(n);
        if (ans == n)
            cout << "Prime\n";
        else
            cout << ans << '\n';
    }
    return 0;
}