#include<iostream>

#include<cstdio>

#include<ctime>

#include<string.h>

#include<stdlib.h>

#define LL long long

using namespace std;

const int S=20;//随机算法判定次数，S越大，判错概率越小

LL ans;

//给定一个数，判断是否是素数(常用long long大数)

LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63

{

    a%=mod;

    b%=mod;

    LL ans=0;

    while(b)

    {

        if(b&1)

        {

            ans=ans+a;

            if(ans>=mod)

            ans=ans-mod;

        }

        a=a<<1;

        if(a>=mod) a=a-mod;

        b=b>>1;

    }

    return ans;

}

LL pow_mod(LL a,LL b,LL mod) // a^b%mod

{

    LL ans=1;

    a=a%mod;

    while(b)

    {

        if(b&1)

        {

            ans=mult_mod(ans,a,mod);

        }

        a=mult_mod(a,a,mod);

        b=b>>1;

    }

    return ans;

}

//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数

//一定是合数返回true,不一定返回false

bool check(LL a,LL n,LL x,LL t)

{

    LL ret=pow_mod(a,x,n);

    LL 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;

}

// Miller_Rabin()算法素数判定

//是素数返回true.(可能是伪素数，但概率极小)

//合数返回false;

bool Miller_Rabin(long long n)

{

    if(n<2)return false;

    if(n==2) return true;

    if( (n&1)==0) return false;//偶数

    LL x=n-1;

    LL t=0;

    while( (x&1)==0 ) { x>>=1;t++;}

    for(int i=0;i<S;i++)

    {

        LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件

        if(check(a,n,x,t))

        return false;//合数

    }

    return true;

}

void find(long long n,int c)

{

    if(n==1)

        return ;

    if(Miller_Rabin(n))

    {

        //m[n]++;

        ans=min(ans,n);

        return ;

    }

    long long p=n;

    while(p>=n)

        p=pollard_rho(p,c--);

    find(p,c);

    find(n/p,c);

}

int main(){

   int a;

   scanf("%d",&a);

   while(a--)

   {

       long long x;

       scanf("%lld",&x);

       if(Miller_Rabin(x))cout<<"prime"<<endl;

       else{

        find(x,12312);

        cout<<ans<<endl;

       }

   }

}