#include<cstdio>

 #include<algorithm>

 using namespace std;

 const int lim=;

 int T,p;

 int phi[lim];

 void init_phi()

 {

     phi[]=;

     for(int i=;i<=lim;i++) phi[i]=i;

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

         if(phi[i]==i)

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

                 phi[j]=phi[j]/i*(i-);

 }

 int mul(int a,int b,int mo)

 {

     int ans=;

     while(b)

     {

         if(b&) ans=(ans%mo+a%mo)%mo;

         b>>=;

         a=a%mo*%mo;

     }

     return ans;

 }

 int ksm(int a,int b,int mo)

 {

     int ans=;

     while(b)

     {

         if(b&) ans=mul(ans,a,mo)%mo;

         b>>=;

         a=mul(a,a,mo)%mo;

     }

     return ans;

 }

 int work(int mod)

 {

     if(mod==) return ;

     return ksm(,work(phi[mod])+phi[mod],mod);

 }

 int main()

 {

     init_phi();

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&p);

         printf("%d\n",work(p));

     }

     return ;

 }