码风优良，仅过一个点，求调。
尝试吸氧分数无变化

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define _rep(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

typedef long long ll;

#define int ll
#define PRIMEN 7

int prime[20] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

mt19937_64 rnd(time(0));

int mul(int a, int b, int mod) {
	int res = 0;
	while (b) {
		if (b & 1) res =  (res + a) % mod;
		a = (a + a) % mod;
		b >>= 1;
	}
	return res % mod;
}

int qpow(int a, int b, int mod) {
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

bool Miller_Rabin(int n, int p) {
	//cout << "MR" << endl;
	if (n == 1) return false;
	int d = n - 1, r = 0;
	while (n & 1 == 0) r++, n >>= 1;
	int x = qpow(p, d, n);
	if (x == 1) return true;
	rep (i, 1, r - 1) {
		if (x == n - 1) return true;
		x *= x;
		x %= n;
	}
	return false;
}

bool isPrime(int n) {
	rep (i, 0, PRIMEN - 1) {
		if (n == prime[i]) return true;
		if (n % prime[i] == 0) return false;
		if (!Miller_Rabin(n, prime[i])) return false;
	}
	return true;
}

int f(int x, int c, int mod) {
	return (x * x + c) % mod;
}

int PollardRho(int x) {
	//cout << "PR" << endl;
	int s = 0, t = 0, c = abs((ll) rnd()) % (x - 1) + 1;
	int target = 1, val = 1, cnt = 0;
	for (target = 1; ; target <<= 1, s = t, val = 1) {
		rep(i, 1, target) {
			cnt++;
			t = f(t, c, x);
			val = val * abs(t - s) % x;
			if (cnt % 127 == 0) {
				int gcd = __gcd(val, x);
				if (gcd > 1) return gcd;
			}
		}
		int gcd = __gcd(val, x);
		if (gcd > 1) return gcd;
	}
}

int ans, T, n;

void solve(int x) {
	//cout << "solve" << endl;
	if (x <= ans || x < 2) return;
	if (isPrime(x)) {
		ans = ans > x ? ans : x;
		return;
	}
	int p = x;
	while (p >= x) p = PollardRho(x);
	while ((x % p) == 0 ) x /= p;
	solve(x), solve(p);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T --> 0) {
		cin >> n;
		ans = 0;
		solve(n);
		if (ans == n) cout << "Prime" << endl;
		else cout << ans << endl;
	}
	return 0;
}