1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 typedef long long ll; 6 using namespace std; 7  8 int get_phi(int x) 9 {10     int res=x;11     for (int i=2;i*i<=x;i++)12     {13         if (x%i==0)14         {15             res-=res/i;16             while (x%i==0) x/=i;17         }18     }19     if (x>1) res-=res/x;20     return res;21 }22 23 int quick_power(ll x,int y,int MOD)//这里有可能会溢出，用long long24 {25     ll ret=1;26     while (y)27     {28         if (y&1) ret=(ret*x)%MOD;29         x=(x*x)%MOD;30         y>>=1;31     }32     return ret;33 }34 35 int solve(int p)36 {37     if (p==1) return 0;38     int k=0;39     while (!(p&1)) p>>=1,++k;40     int phi=get_phi(p);41     int re=solve(phi);42     re=(re-k%phi+phi)%phi;43     int ans=quick_power(2,re,p)%p;44     return (ans<<k);45 }46 47 void init()48 {49     int T;50     scanf("%d",&T);51     while (T--)52     {53         int p;54         scanf("%d",&p);55         printf("%d\n",solve(p));56     }57 }58 59 int main()60 {61     init();62     return 0;63 }