#include<bits/stdc++.h>
using namespace std;

int t,n,idx,r,vis[85],ans[]={0,1,2,2,4,2,4,4,8,2,4,6,8,2,8,6,16,2,4,6,8,4,12,6,16,4,4,4,16,2,12,10,32,4,4,8,8,2
,12,6,16,2,8,6,24,6,12,8,32,6,8,6,8,2,8,10,32,4,4,6,24,2,20,6,64,6,8,8,8,4,16,6,
16,2,4,8,24,14,12,6,32};


void dfs(int x,int step){
    if(step==n) ans[n]++;
    int a=(x+n+step)%n,b=(x+n-step)%n;
    if(!vis[a]){
        vis[a]=1;
        dfs(a,step+1);
        vis[a]=0;
    }
    if(!vis[b]){
        vis[b]=1;
        dfs(b,step+1);
        vis[b]=0;
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        /*
        if(!ans[n]){
            vis[1]=1;
            dfs(1,1);
            vis[1]=0;
        }
        */
        cout<<ans[n]<<endl;
    } 
    return 0;
}