/*

题目：给出一个数 如果是prime 输出prime 否则输出他的最小质因子

Miller Rabin +Poller Rho 大素数判定+大数找质因子

后面这个算法嘛 基于Birthday Paradox

简单点说就是 在 1到100 内去一个数 ai ai==42的概率很小

但是如果取两个数 ai bi ai-bi==42 的概率就会变大

应用到找素因子上 就不用像试除法那样一个一个的试

但是如果枚举ai bi 显然也很slow 那么有一个非常好使(奇怪)的函数

f(x)=x*x+c 这样将x和f(x)%p作为两个数 看看x-f(x) 与p的关系

这里我们不是试试 p%(x-f(x))==0来找 而是 gcd一下 d=(p,(x-f(x)))

d显然是p的因子 然后分解d 这样就ok了 

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#define ll long long

using namespace std;

ll T,ans[],tot;

ll init()

{

    ll x=;char s;s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x;

}

ll gcd(ll a,ll b)

{

    return !b?a:gcd(b,a%b);

}

ll slow_mul(ll a,ll b,ll c)//防止爆掉

{

    a=a%c;b=b%c;

    ll an=;

    while(b)

      {

          if(b&)

            {

                b--;

                an=an+a;

                an=an%c;

          }

        a<<=;a=a%c;b>>=;

      }

    return an;

}

ll Mi(ll a,ll m,ll p)

{

    if(m==)return ;

    ll x=Mi(a,m/,p)%p;

    x=slow_mul(x,x,p);

    if(m&)x=slow_mul(x,a,p);

    return x;

}

ll Pollard_rho(ll p,ll c)

{

    ll i=,k=;

    ll x=rand()%(p-)+;

    ll fx=x;

    while()

      {

          i++;

        x=(slow_mul(x,x,p)+c)%p;

          ll g=gcd(fx-x+p,p);//防止fx-x<0

          if(g!=&&g!=p)return g;//找到一个因子

          if(x==fx)return p;//进入环 换一个随机数

          if(i==k)

            {

                k=k+k;

                fx=x;

          }

      }

}

bool Miller_Rabin(ll n)

{

    if(n==)return ;

    if(n==||!(n&))return ;

    ll m=n-,j=;

    while(!(m&))

      {

          j++;

          m=m>>;

      }

    //srand(unsigned(time(0)));丫丫的poj用srand会RE 我看了好久0.0

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

      {

          ll a=rand()%(n-)+;

          ll x=Mi(a,m,n);

          for(int k=;k<=j;k++)

            {

                ll y=slow_mul(x,x,n);

                if(y==&&x!=&&x!=n-)return ;

                x=y;

          }

        if(x!=)return ;

      }

    return ;

}

void findpri(ll n)//质因数分解n

{

    if(n<=)return;

    if(Miller_Rabin(n))

      {

          ans[++tot]=n;

          return ;

      }

    ll p=n;

    while(p==n)//可能生成的随机数不合适

      p=Pollard_rho(p,rand()%(n-)+);//返回n的一个因子

    findpri(p);

    findpri(n/p);

}

int main()

{

    T=init();

    while(T--)

      {

          ll n=init();

          if(Miller_Rabin(n))//素数先来个判断

            {

                printf("Prime\n");

                continue;

          }

          memset(ans,,sizeof(ans));//所有质因子

          tot=;

          findpri(n);//找质因子

          ll an=ans[];

          for(int i=;i<=tot;i++)

            an=min(an,ans[i]);

          printf("%lld\n",an);

      }

    return ;

}