#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=85;

int vis[maxn],ans;
int cnt[maxn]={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 i,int x,int n)
{
    if(x==n){ans++;return;}//for(int i=1;i<=n;i++)cout<<st[i]<<" ";cout<<endl;return;}
    int y1=(i+x)%n?(i+x)%n:n;
    if(!vis[y1])
    {
        vis[y1]=1;
        dfs(y1,x+1,n);
        vis[y1]=0;
    }
    int y2=i-x<=0?i-x+n:i-x;
    if(!vis[y2])
    {
        vis[y2]=1;
        dfs(y2,x+1,n);
        vis[y2]=0;
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
//    for(int i=1;i<=80;i++)
//    {
//        //int n; cin>>n;
//        memset(vis,0,sizeof(vis));
//        ans=0; vis[1]=1;dfs(1,1,i);
//        cnt[i]=ans;
//    }
    while(t--)
    {
        int n; cin>>n; cout<<cnt[n]<<"\n";
    }
    return 0;
}