#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define lint __int64 lint ans; lint gcd(lint a,lint b) { if ( b == 0 ) return a; return gcd ( b, a % b ); } lint mod_mult ( lint a, lint b, lint n ) { lint ret = 0; a = a % n; while ( b >= 1 ) { if ( b & 1 ) { ret += a; if ( ret >= n ) ret -= n; } a = a << 1; if ( a >= n ) a -= n; b = b >> 1; } return ret; } lint mod_exp ( lint a, lint b, lint n ) { lint ret = 1; a = a % n; while ( b >= 1 ) { if ( b & 1 ) ret = mod_mult(ret,a,n); a = mod_mult(a,a,n); b = b >> 1; } return ret; } bool wintess ( lint a, lint n ) { int i, t = 0; lint m = n - 1, x, y; while ( m % 2 == 0 ) { m >>= 1; t++; } x = mod_exp (a, m, n); for ( i = 1; i <= t; i++ ) { y = mod_exp ( x, 2, n ); if( y==1 && x!=1 && x!=n-1 ) return true; x = y; } if ( y != 1 ) return true; return false; } bool miller_rabin ( lint n, int times = 10 ) { if ( n == 2 ) return true; if ( n == 1 || n % 2 == 0 ) return false; srand ( time(NULL) ); for ( int i = 1; i <= times; i++ ) { lint a = rand() % (n-1) + 1; if ( wintess(a,n) ) return false; } return true; } lint rho ( lint n, int c ) { lint i, k, x, y, d; srand ( time(NULL) ); i = 1; k = 2; y = x = rand() % n; while ( true ) { i++; x = (mod_mult(x,x,n)+c) % n; d = gcd ( y - x, n ); if ( d > 1 && d < n ) return d; if ( y == x ) break; if ( i == k ) { y = x; k *= 2; } } return n; } void pollard ( lint n, int c ) { if ( n == 1 ) return; if ( miller_rabin(n) ) { if(n<ans)ans=n; return; } lint m = n; while ( m >= n ) m = rho ( m, c-- ); pollard ( m, c ); pollard ( n / m, c ); } int main() { lint n; int t; scanf("%d",&t); while ( t-- ) { scanf("%I64d",&n); if ( miller_rabin(n) ) printf("Prime\n"); else { ans = ((lint)1)<<55; pollard(n,181); printf("%I64d\n",ans); } } return 0; }