#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define eps 0.00000001
#define ll long long
#define orz puts("-1")
#define pf(x) printf("%s",x);
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define newline puts("")
#define newspace putchar(' ')
#define lowbit(x) (x&(-x))
#define md(l,r) ((l+r)>>1)
#define lson(p) (p<<1)
#define rson(p) ((p<<1)|1)
#define fi first
#define se second 
#define inf 2147483647
#define mod
#define N 100005
#define lll __int128

namespace fastIO {
	template<class T> void read(T &x) {
		x=0;
		int fl=1;
		char ch=getchar();
		while(ch<'0'||ch>'9') {
			if(ch=='-')fl=-1;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9') {
			x=(x<<1)+(x<<3)+(ch&15);
			ch=getchar();
		}
		x*=fl;
	}
	template<class T> void read(T &x,T &y) {
		read(x);
		read(y);
	}
	template<class T> void read(T &x,T &y,T &z) {
		read(x);
		read(y);
		read(z);
	}
	template<class T> void write(T x) {
		if(x<0) {
			putchar('-');
			x=-x;
		}
		if(x/10)write(x/10);
		putchar(x%10+'0');
	}
	template<class T> void read(T *a,T n) {
		for(int i=1; i<=n; i++)read(a[i]);
	}
	template<class T> void write(T *a,T n) {
		for(int i=1; i<=n; i++)write(a[i]),newspace;
	}
}

using namespace fastIO;

ll maxn, n;
int t;

ll gcd(ll a,ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

ll ksm(ll a,ll b, ll mdd) {
	ll ans = 1;
	for (; b; b >>= 1, a = (lll)(a * a) % mdd) {
		if (b & 1) ans = (lll)ans * a % mdd;
	}
	return ans % mdd;
}

ll f(ll x, ll c, ll mdd) {
	return ((lll)x * x % mdd + c) % mdd;
}

bool Miller_Rabin(ll p, ll c) {
	if (p < 2) return 0;
	if (p == 2 || p == 3) return 1;
	ll d = p - 1, b = 0;
	while (!(d & 1)) d >>= 1, b++;
	ll x = ksm(c, d, p);
	if (x == 1 || x == p - 1) return 1;
	for (int i = 1; i < b; i++) {
		x = (lll)x * x % p;
		if (x == p - 1) break;
	}
	if (x != p - 1) return 0;
	else return 1;
}

bool Prime(ll p) {
	ll prime[] = {2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 43};
	bool flag = 1;
	for (int i = 0; i < 11; i++) {
		if (p == prime[i]) return 1;
		flag &= Miller_Rabin(p, prime[i]);
		//orz;
	}
	return flag;
}

ll Pollard_Rho(ll p) {
	ll s = 0, t = 0;
	ll c = (ll) rand() % (p - 1) + 1;
	for (ll goal = 1; ; goal *= 2, s = t) {
		//orz;
		ll val = 1;
		for (ll step = 1; step <= goal; step++) {
			t = ((lll) t * t + c) % p;
			val = (lll) val * (t >= s ? t - s : s - t) % p;
			if (step % 127 == 0) {
				ll d = gcd(val, p);
				if (d > 1) return d;
			}
		//	write(val);
		//	newline;
		}
		ll d = gcd(val, p);
		if (d > 1) return d;
	}
}

void solve(ll p) {
	if (p < 2 || p <= maxn) return ;
	if (Prime(p)) {
		maxn = max(maxn, p);
		return ;
	}
	ll x = p;
	while (x >= p) x = Pollard_Rho(p);
	while (p % x == 0) p /= x;
	solve(x);solve(p);
}

signed main() {
	int t;
	read(t);
	while (t--) {
		srand(time(0));
		read(n);
		maxn = 0;
		solve(n);
		if (maxn == n) {
			puts("Prime");
		} else {
			write(maxn);
			newline;
		}
	}
	return 0;
}

我觉得该开 __int128 的地方都开了qwq