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

using namespace std;

struct ios {
    inline char read() {
        static const int inlen = 1 << 18 | 1;
        static char buf[inlen], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, inlen, stdin)), s == t ? -1 : *s++;
    }
    template<typename T> inline ios& operator>> (T &x) {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
            if (c11 == -1) return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
        boo && (x = -x);
        return *this;
    }
} fin;

struct exios {
    template<typename _CharT, typename _Traits = char_traits<_CharT>>
    struct typ {
        typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
    };

    friend exios &operator<<(exios &out, int num) {
        if (num < 0) putchar('-'), num = -num;
        if (num >= 10) out << num / 10;
        putchar(num % 10 + '0');
        return out;
    }

    friend exios &operator<<(exios &out, const char * s) { printf("%s", s); return out; }
    friend exios &operator<<(exios &out, string s) { cout << s; return out; }
    friend exios &operator<<(exios &out, typ<char>::end e) { puts(""); return out; }
} fout;

const int maxt = 11;

int t, n;
int p[maxt] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

int power(int base, int freq, int mod) {
    int ans = 1, tmp = base;
    while (freq) {
        if (freq & 1) ans = (i128) ans * tmp % mod;
        freq >>= 1;
        tmp = (i128) tmp * tmp % mod;
    }
    return ans;
}

int gcd(int x,int y) {
	if (!x || !y) return x ^ y;
	int t = __builtin_ctzll(x | y);
	x >>= __builtin_ctzll(x);
	while (y) {
		y >>= __builtin_ctzll(y);
		if (x > y) swap(x, y);
		y -= x;
	}
	return x << t;
}

bool mr(int n) {
    if (n <= 2) return n == 2;
    if (n <= 31) {
        for (int i = 0; i != maxt; ++i) if (n == p[i]) return 1;
        return 0;
    }
    int t = n - 1, r = 0;
    while (!(t & 1)) {
        t >>= 1;
        ++r;
    }
    for (int i = 0; i != maxt; ++i) {
        int s = power(p[i], t, n);
        if (s == 1) continue;
        int j;
        for (j = 1; j <= r; j++) {
            if (s == n - 1) break;
            s = (i128) s * s % n;
        }
        if (j == r + 1) return 0;
    }
    return 1;
}

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

int pr(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return 2;
    if (n % 3 == 0) return 3;
    if (n % 5 == 0) return 5;
    if (mr(n)) return n;
    int x = rand() % (n - 1) + 1, y = x;
    int c = rand() % (n - 3) + 3;
    x = f(x, c, n), y = f(f(y, c, n), c, n);
    for (int len = 1; len <= 128 && x != y; len <<= 1) {
        int m = 1;
        for (int i = 0; i != len; ++i) {
            int g = x > y ? x - y : y - x;
            if (!g) break;
            m = (i128) m * g % n;
            x = f(x, c, n);
            y = f(f(y, c, n), c, n);
        }
        int g = gcd(m, n);
        if (g > 1) return g; 
    }
    return pr(n);
}

int ans = 0;

void mx(int n) {
    if (n <= ans || n <= 1) return;
    if (mr(n)) {
        ans = max(ans, n);
        return;
    }
    int m = pr(n);
    while (n % m == 0) n /= m;
    mx(n), mx(m);
}

signed main() {
    // freopen("P4718_1.in", "r", stdin);
    // freopen("P4718_1.out", "w", stdout);
    
    fin >> t;
    while (t--) {
        fin >> n;
        srand(time(NULL));
        if (mr(n)) {
            puts("Prime");
            continue;
        }
        ans = 0;
        mx(n);
        fout << ans << endl;
    }
    return 0;
}