#include<stdio.h>
#include<string.h>
int comparare(int a[],int b[])
{
 int i;
 if(a[0]>b[0]) return 2;
 else
		if(a[0]<b[0]) return 1;
		else
		{
				i=a[0];
				while(a[i]==b[i]&&i>0)
						i--;
						if(i==0) return 0;
						else
						 if(a[i]>b[i]) return 2;
						 else return 1;
		}
}
int uc(int v[])
{
	int nr;
	switch(v[1])
	{
		case 0:nr=0; break;
		case 1: nr=1; break;
		case 2: nr=v[2]*10+v[1]; if(nr%4==0) nr=6;
														else
															if(nr%4==1) nr=2;
															else
																if(nr % 4 == 2) nr=4;
																else nr=8;
		break;
		case 3:nr=v[2]*10+v[1]; if(nr%4==0) nr=1;
														else
															if(nr%4==1) nr=3;
															else
																if(nr % 4 == 2) nr=9;
																else nr=7;
		break;
		case 4: nr=6; break;
		case 5: nr=5; break;
		case 6: nr=6; break;
		case 7: nr=v[2]*10+v[1]; if(nr%4==0) nr=1;
														else
															if(nr%4==1) nr= 7;
															else
																if(nr % 4 == 2) nr=9;
																else nr=3;
		break;
		case 8: nr=v[2]*10+v[1]; if(nr%4==0) nr=6;
														else
															if(nr%4==1) nr=8;
															else
																if(nr % 4 == 2) nr= 4;
																else nr=2;

		break;
		case 9: nr=9;break;
	}
	return nr;
}
int main()
{
 int t,i,j,q,p,sum;
 FILE *in=fopen("cifra.in","rt");
 FILE *out=fopen("cifra.out","wt");
 char s[102];
 int nr[102],n[102],v[102];
 fscanf(in,"%d",&t);
 for(i=1;i<=t;i++)
 {
		 fscanf(in,"%s",s);
		 p=strlen(s);
		 for(j=0;j<p;j++)
				n[p-j]=s[j]-'0';
		 n[0]=p;
		 for(int k=0;k<=101;k++) v[k]=0;
		 v[1]=1;v[0]=1;
		 sum=0;
		 for( ;comparare(v,n)<2; )
		 {
				sum=(sum+uc(v))%10;
				t=v[1]+1;
				v[1]=t%10;
				t=t/10;
				for(k=2;k<=v[0];k++)
				{
				 t=t+v[k];
				 v[k]=t%10;
				 t=t/10;
				}
				if(t>0) {v[0]++;v[v[0]]=t;}
		 }
		 fprintf(out,"%d\n",sum);
 }
 return 0;
}