/*  * pku1811.c  *  *  Created on: 2011-8-1  *      Author: 王竹 */ #include
     
       #include
      
        #define LL long long LL pmin; LL modular_multi(LL a, LL b, LL c) {
       LL ret;     ret = 0, a %= c; while (b) {
   if (b & 1) {
               ret += a; if (ret > c) {
                   ret -= c;             }         }         a <<= 1; if (a > c) {
               a -= c;         }         b >>= 1;     } return ret; } LL modular_exp(LL a, LL b, LL c) {
       LL ret;     a %= c, ret = 1; while (b) {
   if (b & 1) {
               ret = modular_multi(ret, a, c);         }         a = modular_multi(a, a, c);         b >>= 1;     } return ret; } int miller_rabin(LL n, int times) {
   if (n == 2) {
   return 1;     } if ((n < 2) && (!(n & 1))) {
   return 0;     }     LL te, a, x, y;     te = n - 1; int temp;     temp = 0; while (!(te & 1)) {
           te >>= 1;         temp++;     } int i, j; for (i = 0; i < times; i++) {
           a = rand() % (n - 1) + 1;         x = modular_exp(a, te, n); for (j = 0; j < temp; j++) {
               y = modular_multi(x, x, n); if ((y == 1) && (x != 1) && (x != (n - 1))) {
   return 0;             }             x = y;         } if (x != 1) {
   return 0;         }     } return 1; } LL gcd(LL a, LL b) {
       LL te; if (a < b) {
           te = a, a = b, b = te;     } if (b == 0) {
   return a;     } while (b) {
           te = a % b;         a = b;         b = te;     } return a; } LL pollard_rho(LL n, int c) {
       LL x, y, d, i, k;     x = rand() % (n - 1) + 1;     y = x;     i = 1LL, k = 2LL; while (1) {
           i++;         x = (modular_multi(x, x, n) + c) % n;         d = gcd(y - x, n); if ((1 < d) && (d < n)) {
   return d;         } if (x == y) {
   return n;         } if (i == k) {
               k <<= 1;             y = x;         }     } return -1; } void findFactor(LL n, int c) {
   if (n == 1) {
   return;     } if (miller_rabin(n, 6)) {
   if (n < pmin) {
               pmin = n;         } return;     }     LL p = n; while (p >= n) {
           p = pollard_rho(p, c--);     }     findFactor(p, c);     findFactor(n / p, c); } int main() {
   #ifndef ONLINE_JUDGE     freopen("t.txt", "r", stdin); #endif int T;     LL n; while (scanf("%d", &T) != EOF) {
   while (T--) {
               scanf("%I64d", &n); if (miller_rabin(n, 10)) {
                   printf("Prime\n"); continue;             }             pmin = 1LL << 54;             findFactor(n, 107);             printf("%I64d\n", pmin);         }     } return 0; }