1   2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <algorithm> 6 #define LL long long 7 using namespace std; 8 LL KASE,p; 9 inline LL Get_Phi(LL x)10 {11     LL Ret=x;12     for (LL i=2;i*i<=x;i++)13         if (x%i==0)14         {15             Ret/=i;Ret*=(i-1);16             while (x%i==0) x/=i;17         }18     if (x>1) Ret/=x,Ret*=(x-1);19     return Ret;20 }21 inline LL Pow(LL Base,LL Exp,LL Mod)22 {23     LL Ret=1;24     while (Exp)25     {26         if (Exp&1) Ret=(Ret*Base)%Mod;27         Exp>>=1; Base=(Base*Base)%Mod; 28     }29     return Ret;30 }31 LL Solve(LL p)32 {33     if (p==1) return 0;34     LL Exp=0;35     while (!(p&1)) p>>=1,Exp++;36     LL Phi=Get_Phi(p);37     LL Tmp=Solve(Phi);38     (Tmp+=Phi-Exp%Phi)%=Phi;39     Tmp=Pow(2,Tmp,p)%p;40     return Tmp<<Exp;41      42 }43 int main()44 {45     scanf("%lld",&KASE);46     for (LL Kase=1;Kase<=KASE;Kase++)47     {48         scanf("%lld",&p);49         printf("%lld\n",Solve(p));50     }51     return 0;52 }