第 13 个点一直跑不过，下载数据本地跑一直跑 12 秒左右。

#include <bits/stdc++.h>
#define int __int128

using namespace std;

mt19937 wdz(time(0));
inline int read() {
	int x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x;
}
inline void write(int x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline int gcd(int n, int m) {
	return m == 0 ? n : gcd(m, n % m);
}
inline int fpow(int a, int x, int MOD) {
	a %= MOD;
	int ans = 1;
	while (x) {
		if (x & 1) ans = ans * a % MOD; 
		a = a * a % MOD;
		x >>= 1;
	}
	return ans;
}
int Test[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int test_time = 12;
inline bool millerRabin(int p) {
	if (p == 1) return 0;
	int t = p - 1, k = 0;
	while (!(t & 1)) {
		t >>= 1;
		k++; 
	}
	for (int i = 0; i < test_time; i++) {
		if (p == Test[i]) return 1;
		int a = fpow(Test[i], t, p);
		for (int j = 1; j <= k; j++) {
			if (a * a % p == 1 && a != 1 && a != p - 1) {
				return 0;
			}
			a = a * a % p;
		}
		if (a != 1) return 0;
	}
	return 1;
}
inline int pollard(int n, int c) {
	int x, y, d, i = 1, k = 2;
	x = wdz() % (n - 1) + 1;
	y = x;
	while (1) {
		x = (x * x % n + c) % n;
		d = gcd((x - y + n) % n, n);
		if (1 < d && d < n) return d;
		if (x == y) return n;
		if (++i == k) {
			k <<= 1;
			y = x;
		}
	}
	return 23333333;
}
inline void resolve(int x, int &ans) {
	if (x == 1 || x <= ans) return;
	if (millerRabin(x)) {
		if (ans < x) ans = x;
		return;
	}
	int p = x;
	while (p >= x) {
		p = pollard(x, wdz() % (x - 1) + 1);
	}
	while (x % p == 0) x /= p;
	resolve(x, ans);
	resolve(p, ans);
}
signed main() {
//	freopen("P4718_13.in", "r", stdin);
//	freopen("P4718_13.ans", "w", stdout);
	int qq;
	qq = read();
	while (qq--) {
		int n = read();
		int ans = 0;
		resolve(n, ans);
		if (ans == n) {
			printf("Prime\n");
		} else {
			write(ans);
			putchar('\n');
		}
	}
	
	return 0;
}