#include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define LL long long

 using namespace std;

 LL KASE,p;

 inline LL Get_Phi(LL x)

 {

     LL Ret=x;

     for (LL i=;i*i<=x;i++)

         if (x%i==)

         {

             Ret/=i;Ret*=(i-);

             while (x%i==) x/=i;

         }

     if (x>) Ret/=x,Ret*=(x-);

     return Ret;

 }

 inline LL Pow(LL Base,LL Exp,LL Mod)

 {

     LL Ret=;

     while (Exp)

     {

         if (Exp&) Ret=(Ret*Base)%Mod;

         Exp>>=; Base=(Base*Base)%Mod;

     }

     return Ret;

 }

 LL Solve(LL p)

 {

     if (p==) return ;

     LL Exp=;

     while (!(p&)) p>>=,Exp++;

     LL Phi=Get_Phi(p);

     LL Tmp=Solve(Phi);

     (Tmp+=Phi-Exp%Phi)%=Phi;

     Tmp=Pow(,Tmp,p)%p;

     return Tmp<<Exp;

 }

 int main()

 {

     scanf("%lld",&KASE);

     for (LL Kase=;Kase<=KASE;Kase++)

     {

         scanf("%lld",&p);

         printf("%lld\n",Solve(p));

     }

     return ;

 }