//
//  main.cpp
//  P4718
//
//  Created by mac on 2020/11/30.
//
#include<bits/stdc++.h>
using namespace std;
#define int __int128
int zhi[100001],cnt;
map<int,int>q;
long long maxx;
inline int kuai(int a,int b,int mod)
{
    int ans=1;while(b>0){if(b%2==1)ans=ans*a%mod;a=a*a%mod;b=b/2;}
    return ans;
}
inline int abs(int x){if(x<0)return -x;return x;}
inline int check(int a,int m,int p,int mod)
{
    int tem=kuai(a,m,mod);
    int ans=tem;
    for(int i=1;i<=p;i++)
    {
        ans=tem*tem%mod;;
        if(ans==1&&tem!=1&&tem!=mod-1)return 0;
        tem=ans;
        
    }
    if(ans!=1)return 0;
    return 1;
}
inline int chuli(int n)
{
    if(n<2)return 0;
    if(n==2)return 1;
    if(n%2==0)return 0;
    int p=0;
    int x=n-1;
    while(x%2==0)
    {
        x=x/2;
        p++;
    }
    for(int i=1;i<=30;i++)
    {
        int o=rand()%(n-2)+2;
        if(check(o,x,p,n)==0)return 0;
    }
    return 1;
}
/*int gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}*/
inline int gcd(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    int t=__builtin_ctzll(x|y);
    x>>=__builtin_ctzll(x);
    do
    {
        y>>=__builtin_ctzll(y);
        if(x>y) swap(x,y);
        y-=x;
    }while(y);
    return x<<t;
}
inline int pr(int n,int c)
{
    int x=rand()%(n-2)+1;
    int y=x;
    int i=1,k=2;
    while(1)
    {
        i++;
        x=x*x+c;
        x=x%n;
        int d=gcd(abs(y-x),n);
        if(1<d&&d<n)return d;
        if(y==x)return n;
        if(i==k)
        {
            y=x;
            k<<=1;
        }
    }

}
inline void find(int n,int c)
{
    if(n==1)return;
    if(chuli(n)==1)
    {
        long long  u=n;
        maxx=max(maxx,u);
        return;
    }
    int p=n;
    while(p>=n)p=pr(n,c--);
    find(p,c);
    find(n/p,c);
        
}
inline int read()
{
    int x=0,f=1;
    char ch;
    ch=getchar( );
    while(ch<'0'||ch>'9')ch=getchar( );
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar( );
    }
    return x;
}
inline void write(int x)
{
    int o=10;
    if(x>=o)write(x/o);
    putchar(x%o+'0');
}
signed  main( )
{
    long long  x;
    x=read( );
    while(x--)
    {
        long long  n;
        n=read( );
        maxx=1;
        if(chuli(n)==1)
        {
            printf("Prime\n");
            continue;
        }
        if(q[n]!=0)
        {
            write(q[n]);
            printf("\n");
            continue;
        }
        find(n,200001);
        q[n]=maxx;
        write(maxx);
        printf("\n");
    }
    
}