#include <bits/stdc++.h>
using namespace std;
const int ans[81]={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};
int t,n,res,vis[88];
void dfs(int x,int d) {
    if (vis[x]) return;
    vis[x]=1;
    if (!d) {
        ++res;
        vis[x]=0;
        return;
    }
    dfs((x+n-d)%n,d-1);
    dfs((x+d)%n,d-1);
    vis[x]=0;
}
int main()
{
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        printf("%d\n",ans[n]);
    }
    return 0;
}