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

long long n,i,t;


int citire()
{
char sir[105];
scanf("%s\n",sir);
int n=strlen(sir);
if(n==1)
return sir[0]-'0';
return (sir[n-1]-'0') + 10 * (sir[n-2]-'0');
}

int cifra(long long n)

{
	int s;
	if(n <= 20) 
		s = n;
	else 
		s = n % 20;

	if(s == 1) return 1;
	if(s == 2) return 5;
	if(s == 3) return 2;
	if(s == 4) return 8; 
	if(s == 5) return 3;
	if(s == 6) return 9;
	if(s == 7) return 2;
	if(s == 8) return 8;
	if(s == 9) return 7;
	if(s == 10) return 7;
	if(s == 11) return 8;
	if(s == 12) return 4;
	if(s == 13) return 7;
	if(s == 14) return 3;
	if(s == 15) return 8;
	if(s == 16) return 4;
	if(s == 17) return 1;
	if(s == 18) return 5;
	if(s == 19) return 4;
	if(s == 20) return 4;
	
}

void prel()


{
	scanf("%lld",&t);
	while(t--)
	
	{
	
		n=citire();

		printf("%d\n",cifra(n));

	}
	
}

int main()

{
	
	freopen("cifra.in","r",stdin);
	freopen("cifra.out","w",stdout);
	
	prel();
	
	return 0;
	
}