#include<stdio.h>
#include<string.h>   
int comparare(int a[],int b[])   
{   
 int i;   
 if(a[0]>b[0]) return 2;
 else  
    if(a[0]<b[0]) return 1;
    else  
    {   
        i=a[0];   
        while(a[i]==b[i]&&i>0)   
            i--;   
            if(i==0) return 0;   
            else  
             if(a[i]>b[i]) return 2;
             else return 1;
    }   
} 
int uc(int v[])
{
  int nr;
  switch(v[1])
  {
    case 0:return 0; break;
    case 1: return 1; break;
    case 2: nr=v[2]*10+v[1]; if(nr%4==0) return 6;
                            else
                              if(nr%4==1) return 2;
                              else
                                if(nr % 4 == 2) return 4;
                                else return 8;
    break;
    case 3:nr=v[2]*10+v[1]; if(nr%4==0) return 1;
                            else
                              if(nr%4==1) return 3;
                              else
                                if(nr % 4 == 2) return 9;
                                else return 7;
    break;
    case 4: return 6; break;
    case 5: return 5; break;
    case 6; return 6; break;
    case 7: nr=v[2]*10+v[1]; if(nr%4==0) return 1;
                            else
                              if(nr%4==1) return 7;
                              else
                                if(nr % 4 == 2) return 9;
                                else return 3;
    break;
    case 8: nr=v[2]*10+v[1]; if(nr%4==0) return 6;
                            else
                              if(nr%4==1) return 8;
                              else
                                if(nr % 4 == 2) return 4;
                                else return 2;

    break;
    case 9: return 9;break;
  }
}
int main()   
{   
 int t,i,j,q,p,s;
 FILE *in=fopen("cifra.in","rt");
 FILE *out=fopen("cifra.out","wt");
 char s[102];
 int nr[102],n[102],v[102];
 fscanf(in,"%d",&t);
 for(i=1;i<=t;i++)
 {
     fscanf(in,"%s",s);
     p=strlen(s);
     for(j=0;j<p;j++)
        n[p-j]=s[j]-'0';
     n[0]=p;
     for(int k=0;k<=101;k++) v[k]=0;
     v[1]=1;v[0]=1;
     s=0;
     for( ;comparare(v,n)<2; )
     {
        s=(s+uc(v))%10;
        t=v[1]+1;   
        v[1]=t%10;   
        t=t/10;   
        for(k=2;k<=v[0];k++)   
        {   
         t=t+v[k];   
         v[k]=t%10;   
         t=t/10;   
        }   
        if(t>0) {v[0]++;v[v[0]]=t;}   
     }
     fprintf(out,"%d\n",s);   
 }   
 return 0;   
}