#include<stdio.h>
int main()
{
unsigned long int no,base,no1;
int test_cases,i,j,k,l,mod,rem,temp,flag=1,*s,*e;
char pal[34];
int check[70],step,offset;
scanf("%d",&test_cases);
for(l=0;l<test_cases;l++)
{
scanf("%lu",&no);
no1=no;
step=0;
offset=0;
base=2;
flag=0;
while(flag==0)
{
step=0;
offset=0;
i=0;
j=0;
no=no1;
do
{
if(no1==1)
break;
temp=no/base;
pal[i]=no%base;
step=pal[i]/62;
offset=pal[i]%62;
check[j]=step;
j++;
check[j]=offset;
j++;
i++;
no=temp;
}
while(temp>=base);
if(no1!=1)
{
step=temp/62;
offset=temp%62;
i++;
check[j]=step;
j++;
check[j]=offset;
pal[i]=’\0’;
}
else
{
pal[0]='1';
pal[1]='\0';
check[0]=0;
check[1]=1;
j=1;
}
s=check;
e=&check[j];
for(k=0;k<=j/2;k++)
{
e=e-1;
if(*e!=*s)
{
flag=0;
break;
}
e++;
s++;
if(*e!=*s)
{
flag=0;
break;
}
if(k==j/2)
{
flag=1;
}
s++;
e=e-2;
}
base++;
}
printf("%lu\n",base-1);
}
return(0);
}