#include<stdio.h>
int main()
{
long long int i,k,j,b,u,x,y,z;
long long int N,t;
scanf("%lld",&t);
long long int a[65];
for(i=0;i<t;i++)
{
scanf("%lld",&N);
for(j=1;j<=N;j=j*2)
{
k=j;
}
a[0]=0;
a[1]=1;
z=1;
y=0;
for(b=2;b<60;b++)
{
x=y+z;
y=z;
z=x;
a[b]=x%10;
}
k=k%60;
u=a[k-1];
printf("%lld",u);
}
return 0;
}