#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long int64;int64 gcd(int64 a,int64 b){    return b==0?a:gcd(b,a%b);}int64 mult_mod(int64 a,int64 b,int64 c)//计算a*b%c{    int64 ret=0;    int64 tmp=a;    a%=c,b%=c;//保证a,b小于c，节约计算时间。    while(b)    {        if(b&1)        {            ret+=tmp;            if(ret>c)   ret-=c;        }        tmp<<=1;        if(tmp>c)tmp-=c;        b>>=1;    }    return ret;}int64 pow_mod(int64 a,int64 n,int64 mod)//计算a^n%mod{    int64 ret = 1;    int64 tmp = a%mod;    while(n)    {        if(n & 1)ret = mult_mod(ret,tmp,mod);        tmp = mult_mod(tmp,tmp,mod);        n >>= 1;    }    return ret;}bool check(int64 a,int64 n,int64 x,int64 t)//判断是不是合数{    int64 ret = pow_mod(a,x,n);    int64 last = ret;    for(int i = 1;i <= t;i++)    {        ret = mult_mod(ret,ret,n);        if(ret == 1 && last != 1 && last != n-1)return true;//合数        last = ret;    }    if(ret != 1)return true;    else return false;}bool Miller_Rabin(long long n,int k)//米勒罗宾（判断是不是素数）{    if( n < 2)return false;    if( n == 2)return true;    if( (n&1) == 0)return false;//偶数    long long x = n - 1;    long long t = 0;    while( (x&1)==0 ){x >>= 1; t++;}    srand(time(NULL));    for(int i=0;i
         
          =n) p=pollard_rho(p,c--);//值变化，防止死循环k findfac(p,k); findfac(n/p,k);}int main(){ int T; scanf("%d",&T); int64 ans,n; while(T--) { scanf("%I64d",&n); if(Miller_Rabin(n,5)) printf("Prime\n"); else { tot=0; findfac(n,107); ans=0xfffffff; for(int i=0;i