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

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 3e5 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, cnt;

bool vis[maxn];

void dfs(int x, int p){
    if(p == n) {
        cnt++;
        return;
    }

    if(!vis[(x+p)%n]){
        vis[(x+p)%n] = 1;
        dfs((x+p)%n, p+1);
        vis[(x+p)%n] = 0;
    }

    if(!vis[(x-p+n)%n]){
        vis[(x-p+n)%n] = 1;
        dfs((x-p+n)%n, p+1);
        vis[(x-p+n)%n] = 0;
    }
}

int ans[] = {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 main(){
    //freopen("in.txt", "r", stdin);
    /*
    int m;
    while(cin>>m){
        cout << "{";
        for(n = 1; n <= m; n++){
            if(n > 1) putchar(',');
            memset(vis, 0, sizeof(n));
            cnt = 0; vis[0] = 1; dfs(0, 1);
            cout << cnt;
        }
        cout << "};" << endl;
    }
    */
    int T; cin >> T;
    while(T--){
        cin >> n;
        cout << ans[n-1] <<endl;
    }
    return 0;
}