// 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;

}