#include <bits/stdc++.h>
using namespace std;
int t,o[10000001];
void ol(){
    o[1]=1;
    for(int i=2;i<=10000000;i++){
        o[i]=i-1;
    }
    for(int i=2;i<=10000000;i++){
        if(o[i]==i-1){
            for(int j=i*2;j<=10000000;j+=i){
                o[j]=o[j]/i*(i-1);
            }
        }
    }
}
int xs(int x,int n,int p){
    int a=1;
    while(n){
        if(n&1){
            a*=x;
            a%=p;
        }
        x=x%p*(x%p)%p;
        n>>=1;
    }
    return a;
}
int f(int p){
    if(p==1){
        return 0;
    }else{
        return xs(2,o[p],p)*xs(2,f(o[p]),p)%p;
    }
}
int main(){
    cin>>t;
    ol();
    for(int i=1;i<=t;i++){
        int p;
        cin>>p;
        int xx=f(p);
        cout<<xx<<"\n";
    }
}