#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long

const ll mod_1=1e9+7;
const ll mod_2=998244353;

const double eps_1=1e-5;
const double eps_2=1e-10;

const int maxn=1e5+10;


int n,sum=0;
bool vis[100];


void dfs(int i,int step)
{

    int pos;

    if (step==n)
    {
        sum++;
        return;
    }

    pos=(i+step+n)%n;
    if (!vis[pos])
    {
        vis[pos]=1;
        dfs(pos,step+1);
        vis[pos]=0;
    }

    pos=(i-step+n)%n;
    if (!vis[pos])
    {
        vis[pos]=1;
        dfs(pos,step+1);
        vis[pos]=0;
    }
}



int main()
{
    int i;
//    for (i=1;i<=80;i++)
//    {
//
//        n=i;
//        sum=0;
//
//        vis[0]=1;
//        dfs(0,1);   ///0
//
//
////        printf("n=%d sum=%d\n",i,sum);
//
//        printf("%d , ",sum);
//    }

    int f[100]={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;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        sum=0;

//        vis[0]=1;
//        dfs(0,1);   ///0

        printf("%d\n",f[n]);
    }
    return 0;
}