各位义父帮帮我吧！

#include <bits/stdc++.h>
#define int long long
using namespace std;
int Prime[7] = {2, 3, 5, 7, 11, 13, 37};
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
template <class T>
T randint(T l, T r = 0) {
    static mt19937 eng(time(0));
    if (l > r)
        swap(l, r);
    uniform_int_distribution<T> dis(l, r);
    return dis(eng);
}
int Qpow(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p, b >>= 1; 
    }
    return res;
}
bool Miller_Rabin(int x, int b) {
    int d = x - 1;
    while (d) {
        int res = Qpow(b, d, x);
        if (res != 1 and res != x - 1) return false;
        if (res & 1 or res == x - 1) return true;
        d >>= 1; 
    }
    return true;
}
bool isP(int x) {
    if (x <= 1) return false;
    for (int i = 0; i < 7; ++i) {
        if (x == Prime[i]) return true;
        if (x % Prime[i] == 0) return false;
    }
    return Miller_Rabin(x, 37) and Miller_Rabin(x, 13);
}
int f(int x, int c, int p) {return ((__int128)x * x + c) % p;}
int Pollard_Rho(int x) {
    if (x == 4) return 2;
    if (isP(x)) return x;
    while (1) {
        int c = randint <int> (1, x - 1);
        int t = 0, r = 0, p = 1, q;
        do {
            for (int i = 0; (t = f(t, c, x), r = f(f(r, c, x), c, x)), i < 128; ++i) {
                if (t == r or (q = (__int128)p * abs(t - r) % x) == 0) break;
                p = q;
            }
            int d = gcd(p, x);
            if (d > 1) return d;
        } while (t != r);   
    }
}
int Find(int x) {
    int fac = Pollard_Rho(x);
    if (fac == x) return x;
    else return max(Find(fac), Find(x / fac));
}
void solve() {
    int n; cin >> n;
    int k = Find(n);
    if (k == n) puts("Prime");
    else cout << k << '\n';
}
signed main() {
    int T; cin >> T;
    while (T--) solve();
    return 0;
}