#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long t,p;
long long f_pow(long long a,long long b,long long p)
{
    long long ans=1,base=a;
    while (b)
    {
        if (b&1) ans=(ans*base)%p;
        base=(base*base)%p;
        b>>=1;
    }
    return ans;
}
long long phi(long long x)
{
    long long ret1=1,ret2=1,up=sqrt(x),reg=x;
    for (long long i=2;i<=up;i++)
    {
        if (x%i==0)
        {
            ret1*=(i-1);ret2*=i;
            while (x%i==0) x/=i;
        }
    }
    if (x!=1) {ret1*=(x-1);ret2*=x;}
    return reg/ret2*ret1;
}
long long ask(long long p)
{
    if (p==1) return 0;
    return f_pow(2,ask(phi(p))+phi(p),p);
}
int main()
{
    scanf("%lld",&t);
    for (long long i=1;i<=t;i++)
    {
        scanf("%lld",&p);
        printf("%lld\n",ask(p));
    }
    return 0;
}