#include<fstream>

using namespace std;

ifstream fin ("cifra.in");
ofstream fout ("cifra.out");

long long s[23]={1,5,2,8,3,9,2,8,7,7,8,4,7,3,8,4,1,5,4,4};

int main ()
{
    
    int a,i,k,n;
    fin>>n;
    for(i=1;i<=n;i++)
    {
                     fin>>k;
                     k=k%20-1;
                     fout<<s[k]<<"\n";
}
return 0;
}