#include <stdio.h>
#include <math.h>
int v[31]={1,5,2,8,3,9,2,8,7,7,8,4,7,3,8,4,1,5,4,4,5,9,6,2,7,3,6,2,1,1};
int main()
{
	int t,i,cif,uc,n,j,k;
	FILE *f,*g;
	f=fopen("cifra.in","r");
	g=fopen("cifra.out","w");
	fscanf(f,"%d",&t);
	for(i=0;i<t;i++)
	{
		fscanf(f,"%d",&n);
		if(n<=30)
			fprintf(g,"%d\n",v[n-1]);
		else
		{
			cif=1; //ultima cifra 1^1 + 2^2 + ... + 30^30 = 1
			k=31;
			if(n>10000)
			{
				cif=0;
				k=10001;
			}
			else
			if(n>1000)
			{
				cif=0;
				k=1001;
			}
			else
				if(n>500)
				{
					cif=0;
					k=501;
				}
				else
					if(n>100)
					{
						cif=0;
						k=101;
					}
					else
						if(n>50)
						{
							cif=5;
							k=51;
						}
			for(j=k;j<=n;j++)
				{
					uc=j%10;
					if(uc==0 || uc==1 || uc==5 || uc==6)
						cif+=uc;
					else
					{
						uc=j%4;
						if(!uc)
							uc=4;
						cif+=(int)pow(j%10,uc)%10;
					}
				}
			fprintf(g,"%d\n",cif%10);
		}
	}
	fcloseall();
	return 0;
}