var a:array[0..19] of integer;
i,n,x:integer;
g,f:text;
begin
assign(f,'cifra.in');reset(f);
assign(g,'cifra.out');rewrite(g);
a[0]:=4;
a[1]:=1;
a[2]:=5;
a[3]:=2;
a[4]:=8;
a[5]:=3;
a[6]:=9;
a[7]:=2;
a[8]:=8;
a[9]:=7;
a[10]:=7;
a[11]:=8;
a[12]:=4;
a[13]:=7;
a[14]:=3;
a[15]:=8;
a[16]:=4;
a[17]:=1;
a[18]:=5;
a[19]:=4;
readln(f,n);
for i:=1 to n do begin
readln(f,x);
writeln(g,a[x mod 20]);
end;
close(f);
close(g);
readln;
end.