#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=100,P=998244353;
int n;
int ans[maxn];
//int mark[maxn];
//void dfs(int x,int p){
//    if(p==n){
//        ans++;
//        return;
//    }
//    if(!mark[(x+p-1)%n+1]){
//        mark[(x+p-1)%n+1]=1;
//        dfs((x+p-1)%n+1,p+1);
//        mark[(x+p-1)%n+1]=0;
//    }
//    if(!mark[(x-p+n-1)%n+1]){
//        mark[(x-p+n-1)%n+1]=1;
//        dfs((x-p+n-1)%n+1,p+1);
//        mark[(x-p+n-1)%n+1]=0;
//    }
//    
//}
//int solve(int x){
//    n=x;
//    ans=0;
//    mark[1]=1;
//    dfs(1,1);
//    return ans;
//}
int main(){
ans[1]=1;
ans[2]=2;
ans[3]=2;
ans[4]=4;
ans[5]=2;
ans[6]=4;
ans[7]=4;
ans[8]=8;
ans[9]=2;
ans[10]=4;
ans[11]=6;
ans[12]=8;
ans[13]=2;
ans[14]=8;
ans[15]=6;
ans[16]=16;
ans[17]=2;
ans[18]=4;
ans[19]=6;
ans[20]=8;
ans[21]=4;
ans[22]=12;
ans[23]=6;
ans[24]=16;
ans[25]=4;
ans[26]=4;
ans[27]=4;
ans[28]=16;
ans[29]=2;
ans[30]=12;
ans[31]=10;
ans[32]=32;
ans[33]=4;
ans[34]=4;
ans[35]=8;
ans[36]=8;
ans[37]=2;
ans[38]=12;
ans[39]=6;
ans[40]=16;
ans[41]=2;
ans[42]=8;
ans[43]=6;
ans[44]=24;
ans[45]=6;
ans[46]=12;
ans[47]=8;
ans[48]=32;
ans[49]=6;
ans[50]=8;
ans[51]=6;
ans[52]=8;
ans[53]=2;
ans[54]=8;
ans[55]=10;
ans[56]=32;
ans[57]=4;
ans[58]=4;
ans[59]=6;
ans[60]=24;
ans[61]=2;
ans[62]=20;
ans[63]=6;
ans[64]=64;
ans[65]=6;
ans[66]=8;
ans[67]=8;
ans[68]=8;
ans[69]=4;
ans[70]=16;
ans[71]=6;
ans[72]=16;
ans[73]=2;
ans[74]=4;
ans[75]=8;
ans[76]=24;
ans[77]=14;
ans[78]=12;
ans[79]=6;
ans[80]=32;
//    freopen("data.in","r",stdin);
//    freopen("std.out","w",stdout);
    
//    for(int i=2;i<=80;i++){
//        cout<<"ans["<<i<<"]="<<solve(i)<<endl; 
//    }
    
    int QuQ;cin>>QuQ;
    while(QuQ--){
        int tmp;
        cin>>tmp;
        cout<<ans[tmp]<<endl;
//        cout<<solve(tmp)<<endl;
    }
    
    return 0;
}