#include <cstdio>
#include <stdlib.h>
using namespace std;
 	int T,i,j,cifra,nr,k;
	 bool ok=0;
	char *v = (char*) calloc (103,sizeof(char));

int main(){
	
	freopen("cifra.in", "r", stdin);
	freopen("cifra.out", "w", stdout);
	


    scanf ("%d", &T);
 
   	while (T>=0){
   		
   		i=0;
   		cifra=0;
   		while (v[i-1]!='\n'){
   			scanf ("%c", &v[i]);
   			if (v[0]=='\n') {break;}
   			i++;
   		}
   		
   		i=i-1;
   		ok=0;
   		
   		while (ok==0) {
   			ok=1;
   			if (i!=0) nr=v[i-1]*10+v[i];
   			else nr=v[0];
   			//retinerea ultimei cifre
   			switch (v[i]){
   				case '1': cifra=(cifra+1)%10; break;
   				case '2': if(nr%4==0) cifra=(cifra+6)%10;
   						 else cifra=(cifra+4)%10;
				   		 break;
   				case '3': if(nr%4==1) cifra=(cifra+3)%10;
   						 else cifra=(cifra+7)%10;
				   		 break;
   				case '4': cifra=(cifra+6)%10; break;
   				case '5': cifra=(cifra+5)%10; break;
   				case '6': cifra=(cifra+6)%10; break;
   				case '7': if(nr%4==1) cifra=(cifra+7)%10;
   						 else cifra=(cifra+3)%10;
				   		 break;
   				case '8': if(nr%4==0) cifra=(cifra+6)%10;
   						 else cifra=(cifra+4)%10;
				   		 break;
   				case '9': cifra=(cifra+9)%10; break;
   			}
   			//scadere cate 1 din numar
   			if (v[i]=='0') {
			   v[i]=9;
			   k=i-1;
			   while (v[k]=='0'){
			   		v[k]=9;
			   		k--;
			   }
			   v[k]=v[k]-1;
			}	
			else v[i]--;
			
			//verificare daca numarul este 0
   			for (j=0; j<=i-1; j++) {
   				if (v[j]!='0'){ok=0;}
   			}	
			  	
		}
		if (cifra!=0){printf ("%d\n", cifra);}
   		T--;
   	}
    return 0;
}