#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=1e7+;

 int pri[N],npr[N],phi[N];

 long long T,mod;

 void prework()

 {

     phi[]=,npr[]=true;

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

     {

         if(!npr[i]) pri[++sz]=i,phi[i]=i-;

         for(int j=;j<=sz&&i*pri[j]<=;j++)

         {

             npr[i*pri[j]]=true;

             phi[i*pri[j]]=phi[i]*pri[j];

             if(i%pri[j]) phi[i*pri[j]]-=phi[i]; else break;

         }

     }

 }

 long long qpow(long long x,long long k,long long md)

 {

     if(k==) return x%md;

     long long tmp=qpow(x,k/,md);

     return k%?tmp*tmp%md*x%md:tmp*tmp%md;

 }

 long long Gas(long long md)

 {

     return md==?:qpow(,Gas(phi[md])+phi[md],md);

 }

 int main ()

 {

     scanf("%lld",&T),prework();

     while(T--)

     {

         scanf("%lld",&mod);

         printf("%lld\n",Gas(mod));

     }

     return ;

 }