#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

ll p;

int phi[N], pri[N], mark[N];

void Init()

{

    phi[] = ;

    for(int i = ; i <= ; ++i)

    {

        if(!mark[i])

        {

            pri[++pri[]] = i;

            phi[i] = i - ;

        }

        for(int j = ; j <= pri[] && (ll)i * (ll)pri[j] <= ; ++j)

        {

            mark[i * pri[j]] = ;

            if(i % pri[j] == )

            {

                phi[i * pri[j]] = phi[i] * pri[j];

                break;

            }

            phi[i * pri[j]] = phi[i] * (pri[j] - );

        }

    }

}

inline ll power(ll x, ll t, ll p)

{

    ll ret =  % p; x %= p;

    for(; t; t >>= , x = x * x % p) if(t & ) ret = ret * x % p;

    return ret;

}

ll f(ll x) // 2^2^2...%p=

{

    if(x == ) return ;

    return power(2ll, f(phi[x]) + (ll)phi[x], x);

}

int main()

{

    Init();

    int T; scanf("%d", &T);

    while(T--)

    {

        scanf("%lld", &p);

        printf("%lld\n", f(p));

    }

    return ;

}