论O(1)快速乘和O(logn)快速乘的差距….

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

ll shai[10]={2,3,5,7,11,13,17,19,23,29};

ll mul(ll a,ll b,ll p){

    ll d=((long double)a/p*b+1e-8);

    ll res=a*b-d*p;

    res=res<0?res+p:res;

    return res;

}

ll pow(ll x,ll y,ll mod){

    x%=mod;ll res=1;

    while(y){

        if(y&1)res=mul(res,x,mod);

        x=mul(x,x,mod),y>>=1;

    }return res;

}

bool check(ll a,ll n,ll r,int s){

    ll x=pow(a,r,n),pre=x;

    for(int i=1;i<=s;i++){

        x=mul(x,x,n);

        if(x==1&&pre!=1&&pre!=n-1)return 0;

        pre=x;

    }return x==1;

}

bool miller_rabin(ll n){

    if(n<=1)return 0;

    ll r=n-1,s=0;

    while(!(r&1))r>>=1,s++;

    for(int i=0;i<10;i++){

        if(shai[i]==n)return 1;

        if(!check(shai[i],n,r,s))return 0;

    }return 1;

}

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

ll prime_factor(ll n,ll c){

    ll k=2,x=rand()%n,y=x,p=1;

    for(int i=1;p==1;i++){

        x=(mul(x,x,n)+c)%n;

        p=gcd(abs(x-y),n);

        if(i==k)y=x,k<<=1;

    }return p;

}

ll ans,xx;int cases;

void pollard_rho(ll n){

    if(n==1)return;

    if(miller_rabin(n)){ans=max(ans,n);return;}

    ll p=n;

    while(p==n)p=prime_factor(n,rand()%(n-1));

    pollard_rho(p),pollard_rho(n/p);

}

int main(){

    scanf("%d",&cases);

    while(cases--){

        ans=0,scanf("%lld",&xx),pollard_rho(xx);

        if(ans!=xx)printf("%lld\n",ans);

        else puts("Prime");

    }

}



//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

typedef unsigned long long ll;

ll shai[10]={2,3,5,7,11,13,17,19,23,29};

ll mul(ll x,ll y,ll mod){

    x%=mod;ll res=0;

    while(y){

        if(y&1)res=(res+x)%mod;

        x=(x+x)%mod;

        y>>=1;

    }return res;

}

ll pow(ll x,ll y,ll mod){

    x%=mod;ll res=1;

    while(y){

        if(y&1)res=mul(res,x,mod);

        x=mul(x,x,mod),y>>=1;

    }return res;

}

bool check(ll a,ll n,ll r,int s){

    ll x=pow(a,r,n),pre=x;

    for(int i=1;i<=s;i++){

        x=mul(x,x,n);

        if(x==1&&pre!=1&&pre!=n-1)return 0;

        pre=x;

    }return x==1;

}

bool miller_rabin(ll n){

    if(n<=1)return 0;

    ll r=n-1,s=0;

    while(!(r&1))r>>=1,s++;

    for(int i=0;i<10;i++){

        if(shai[i]==n)return 1;

        if(!check(shai[i],n,r,s))return 0;

    }return 1;

}

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

ll prime_factor(ll n,ll c){

    ll k=2,x=rand()%n,y=x,p=1;

    for(int i=1;p==1;i++){

        x=(mul(x,x,n)+c)%n;

        p=gcd(abs((long long)x-(long long)y),(long long)n);

        if(i==k)y=x,k<<=1;

    }return p;

}

ll ans,xx;int cases;

void pollard_rho(ll n){

    if(n==1)return;

    if(miller_rabin(n)){ans=max(ans,n);return;}

    ll p=n;

    while(p==n)p=prime_factor(n,rand()%(n-1));

    pollard_rho(p),pollard_rho(n/p);

}

int main(){

    scanf("%d",&cases);

    while(cases--){

        ans=0,scanf("%llu",&xx),pollard_rho(xx);

        if(ans!=xx)printf("%llu\n",ans);

        else puts("Prime");

    }

}