#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#include<list>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
const int maxn = 2e6 + 7;
const int INF = (1 << 31) - 1;
const int mod = 1e9 + 7;
const double PI = acos(-1);
inline ll ksm(ll a, ll p) { ll res = 1; while (p) { if (p & 1)res *= a; a *= a; p >>= 1; }return res; }
int n, cnt;
bool dfs(int pos, vector<bool>& vis,int d) {
    if (d == n) {
        cnt++;
        return 1;
    }
    int npos = ((pos - d) % n + n) % n;
    if (vis[npos] == 0) {
        vis[npos] = 1;
        dfs(npos, vis, d + 1); vis[npos] = 0;
    }
    npos = ((pos + d) % n + n) % n;
    if (vis[npos] == 0) {
        vis[npos] = 1;
        dfs(npos, vis, d + 1); vis[npos] = 0;
    }
    return 0;
}
ll 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 work() {
    /*for (int i = 2; i <= 80; ++i) {
        n = i;
        vector<bool> vis(n, 0);
        vis[1] = 1;
        cnt = 0;
        dfs(1, vis, 1);
        ans[i] = cnt;
    }
    for (int i = 1; i <= 80; ++i)cout << ans[i] << ",\n"[i == 80];*/
    int n; cin >> n;
    cout << ans[n] << '\n';
    
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for (int i = 1; i <= T; ++i) {
        //cout << "Case #" << i << ": ";
        work();
    }
}