#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e7+5;
int phi[N],a[N],cnt,p;
bool vis[N];
inline int ksm(int a,int b,int mod){
	int res=1,x=a;
	while(b){
		if(b&1) res=(res*x)%mod;
		x=(x*x)%mod;
		b>>=1;
	}
	return res;
}
inline int get_ans(int mod){
	return (mod==1)?0:ksm(2,get_ans(phi[mod])+phi[mod],mod);
}
inline void pre(int n){
	phi[1]=1;
	vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			a[++cnt]=i;
			phi[i]=i-1;		
		}
		for(int j=1;j<=cnt&&i*a[j]<=n;i++){
			if(i%a[j]==0){
				phi[i*a[j]]=phi[i]*a[j];
				break;
			}else{
				phi[i*a[j]]=phi[i]*(a[j]-1);
			}
		}
	}
}
int t,n;
signed main(){
	pre(1e6);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&p);
		printf("%lld\n",get_ans(p));
	}
}