#include <iostream>
using namespace std;
const int MAXN = 85;
bool vis[MAXN];
int a[MAXN];
int n;
/*
3
3

*/
int dfs(int x,int len,int cnt)
{//当前位置、当前需要移动的距离 
    if(vis[x])    return 0;
    if(cnt == n)
    {
        if(len == n)    return 1;
        return 0;
    }
    vis[x] = 1;
    
    int ans = 0;
    int now = dfs((x + len)%n,len + 1,cnt + 1);
    ans += now;
    
    now = dfs((x - len + n)%n,len + 1,cnt + 1);
    ans += now;
    
    vis[x] = 0;
    return ans;
}
///*

//*/
int main()
{
    a[2] = 2;
a[3] = 2;
a[4] = 4;
a[5] = 2;
a[6] = 4;
a[7] = 4;
a[8] = 8;
a[9] = 2;
a[10] = 4;
a[11] = 6;
a[12] = 8;
a[13] = 2;
a[14] = 8;
a[15] = 6;
a[16] = 16;
a[17] = 2;
a[18] = 4;
a[19] = 6;
a[20] = 8;
a[21] = 4;
a[22] = 12;
a[23] = 6;
a[24] = 16;
a[25] = 4;
a[26] = 4;
a[27] = 4;
a[28] = 16;
a[29] = 2;
a[30] = 12;
a[31] = 10;
a[32] = 32;
a[33] = 4;
a[34] = 4;
a[35] = 8;
a[36] = 8;
a[37] = 2;
a[38] = 12;
a[39] = 6;
a[40] = 16;
a[41] = 2;
a[42] = 8;
a[43] = 6;
a[44] = 24;
a[45] = 6;
a[46] = 12;
a[47] = 8;
a[48] = 32;
a[49] = 6;
a[50] = 8;
a[51] = 6;
a[52] = 8;
a[53] = 2;
a[54] = 8;
a[55] = 10;
a[56] = 32;
a[57] = 4;
a[58] = 4;
a[59] = 6;
a[60] = 24;
a[61] = 2;
a[62] = 20;
a[63] = 6;
a[64] = 64;
a[65] = 6;
a[66] = 8;
a[67] = 8;
a[68] = 8;
a[69] = 4;
a[70] = 16;
a[71] = 6;
a[72] = 16;
a[73] = 2;
a[74] = 4;
a[75] = 8;
a[76] = 24;
a[77] = 14;
a[78] = 12;
a[79] = 6;
a[80] = 32;
    int ans;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n == 1)
        puts("1");
        else
        {
            printf("%d\n",a[n]);
        }
    }
    return 0;
}