#include <stdio.h>
#include <string.h>

int T;
unsigned h;
char N[100];
FILE *f=fopen("cifra.in","rt");
FILE *g=fopen("cifra.out","wt");

void Csokkent(unsigned H)
{	if (N[H-1])
		N[H-1]--;
	else
	{	N[H-1]=9;
		Csokkent(H-1);
	}
}

int Utolso()
{	char uSzam=N[h-1];
	switch (uSzam)
	{	case 2:
		case 8: if ((N[h-1]+10*N[h-2])%4) return 4;
				else return 6;
		case 3: if ((N[h-1]+10*N[h-2])%4==1) return 3;
				else return 7;
		case 4: return 6;
		case 7: if ((N[h-1]+10*N[h-2])%4==1) return 7;
				else return 3;
		default: return uSzam;
	}
}

int Szamol()
{	int v=0;
	while (N[h-1])
	{	v+=Utolso();
		v%=10;
		Csokkent(h);
	}
	return v;
}

int main()
{	fscanf(f,"%d",&T);
	for (int i=0;i<T;i++)
	{	fscanf(f,"%s",N);
		h=strlen(N);
		for (unsigned j=0;j<h;j++)
			N[j]-=48;
		fprintf(g,"%d\n",Szamol());
	}
	fclose(f);
	fclose(g);
}