1 //2017-08-04
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long 
 7 
 8 using namespace std;
 9 
10 const int N = 1000010;
11 char b[N];
12 ll a, c;
13 
14 ll quick_pow(ll a, ll n, ll MOD){
15     ll ans = 1;
16     while(n){
17         if(n&1)ans = ans*a%MOD;
18         a = a*a%MOD;
19         n>>=1;
20     }
21     return ans;
22 }
23 
24 ll phi(ll n){
25     ll ans = n;
26     for(ll i = 2; i*i <= n; i++){
27         if(n%i==0){
28             ans -= ans/i;
29             while(n%i==0)
30                 n /= i;
31         }
32     }
33     if(n > 1)ans = ans - ans/n;
34     return ans;
35 }
36 
37 ll solve(int p){
38     if(p <= 1)return 0;
39     ll k = 0, powk = 1;
40     while(p%2==0){
41         k++;
42         powk *= 2;
43         p>>=1;
44     }
45     ll phip = phi(p);
46     k %= phip;
47     ll num = (solve(phip)+phip-k)%phip;
48     return quick_pow(2, num, p)%p*powk;
49 }
50 
51 int main()
52 {
53     int T, p;
54     cin>>T;
55     while(T--){
56         cin>>p;
57         cout<<solve(p)<<endl;
58     }
59     return 0;
60 }