#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x*=10;x+=c-'0';
        c=getchar();
    }
    return x*f;
}
//int head[N],last;
//struct u2003{
//    int nx,b;
//}e[M];
//inline void build(int a,int b){
//    e[++last].b=b;
//    e[last].nx=head[a];
//    head[a]=last;
//}
int 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};
int main(){
    int t,n;
    t=read();
    for(int i=1;i<=t;i++){
        n=read();
        printf("%d\n",ans[n]);
    }
}