#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define LL long long
#define maxn 10000010
using namespace std;
LL T,a1,phi[maxn];
int p[maxn],lp;
bool bk[maxn];
LL ksm(LL x,LL y,LL mod){LL ans=(LL)1;while(y){if(y&1)ans=(ans*x)%mod;x=(x*x)%mod;y>>=1;}return ans;}
LL dfs(LL mod){
	if(mod==1)return 0;
	return ksm((LL)2,dfs(phi[mod])%phi[mod]+phi[mod],mod);
}
int main(){
	freopen("hsgetz.in","r",stdin);
	freopen("hsgetz.out","w",stdout);
	phi[1]=1;
	for(int i=2;i<=maxn-10;i++){
		if(!bk[i])p[++lp]=i,phi[i]=i-1;
		for(int j=1;j<=lp;j++){
			if(i*p[j]>maxn-10)break;
			bk[i*p[j]]=1;
			if(i%p[j]==0){phi[i*p[j]]=phi[i]*(LL)p[j];break;}
			phi[i*p[j]]=phi[i]*((LL)p[j]-(LL)1);
		}
	}
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&a1);
		printf("%lld\n",dfs(a1));
	}
	return 0;
}