#include<stdio.h>

long long n,i,t;

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);
	for(i=1;i<=t;i++)
	{
	
		scanf("%lld",&n);
		
		printf("%d\n",cifra(n));
		
	}
	
}

int main()

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