// bzoj3884#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std; const int maxn=10000010;int phi[maxn],vis[maxn],p[maxn];void calphi() {	phi[1]=1;	for (int i=2;i<maxn;i++) {		if (!vis[i]) {p[++p[0]]=i;phi[i]=i-1;}		for (int j=1;j<=p[0];j++) {			if (p[j]*i>maxn) break;			vis[p[j]*i]=1;			if (i%p[j]==0) {phi[p[j]*i]=phi[i]*p[j];break;}			else phi[p[j]*i]=phi[p[j]]*phi[i];		}	}}int power(int a,int b,int c) {	int res=1;	while (b) {		if (b&1) res=(LL)res*a%c;		b>>=1;a=(LL)a*a%c;	}	return res;}int solve(int p) {	if (p==1) return 0;	int res=solve(phi[p])+phi[p];	return power(2,res,p);}int main() {	calphi();	int T,P;scanf("%d",&T);	while (T--) {		scanf("%d",&P);		printf("%d\n",solve(P));	}    return 0;}