var n:longint;
t,i:integer;
f,g:text;
begin
assign(f,'cifra.in');reset(f);
assign(g,'cifra.out');rewrite(g);
readln(f,t);
for i:=1 to t do begin
readln(f,n);
if (n=1) or (n mod 100=29) or (n mod 100=30) or (n mod 100=45) or (n mod 100=66) or (n mod 100=73) or (n mod 100=77) or
(n mod 100=82)
or (n mod 100=94) or (n mod 100=98) then writeln(g,'1');
if (n=3) or (n=7) or (n mod 100=12) or (n mod 100=24) or (n mod 100=28) or (n mod 100=31) or (n mod 100=59) or
(n mod 100=60) or (n mod 100=75) or (n mod 100=96) then writeln(g,'2');
if (n=5) or (n mod 100=26) or (n mod 100=33) or (n mod 100=37) or (n mod 100=42) or (n mod 100=54) or (n mod 100=58)
or (n mod 100=61) or (n mod 100=89) or (n mod 100=90) then writeln(g,'3');
if (n mod 100=19) or (n mod 100=20) or (n mod 100=35) or (n mod 100=56) or (n mod 100=63) or (n mod 100=67) or
(n mod 100=72) or (n mod 100=84) or (n mod 100=88) or (n mod 100=91) then writeln(g,'4');
if (n mod 100=96) or (n mod 100=12) or (n mod 100=24) or (n mod 100=28) or (n mod 100=31) or (n mod 100=59) or
(n mod 100=60) or ( n mod 100=75) or (n=2) or (n=7) then writeln(g,'5');
if (n mod 100=16) or (n mod 100=23) or (n mod 100=27) or (n mod 100=32) or (n mod 100=44) or (n mod 100=48) or
(n mod 100=51) or ( n mod 100=79) or (n mod 100=80) or (n mod 100=95) then writeln(g,'6');
if (n mod 100=10) or (n mod 100=9) or (n mod 100=25) or (n mod 100=46) or (n mod 100=53) or (n mod 100=57) or
(n mod 100=62) or ( n mod 100=74) or (n mod 100=78) or (n mod 100=81) then writeln(g,'7');
if (n mod 100=4) or (n mod 100=8) or (n mod 100=11) or (n mod 100=39) or (n mod 100=40) or (n mod 100=55) or
(n mod 100=76) or ( n mod 100=83) or (n mod 100=87) or (n mod 100=92) then writeln(g,'8');
if (n mod 100=6) or (n mod 100=13) or (n mod 100=17) or (n mod 100=22) or (n mod 100=34) or (n mod 100=38) or
(n mod 100=41) or ( n mod 100=69) or (n mod 100=70) or (n mod 100=85) then writeln(g,'9');
if (n mod 100=15) or (n mod 100=36) or (n mod 100=43) or (n mod 100=47) or (n mod 100=52) or (n mod 100=64) or
(n mod 100=68) or ( n mod 100=71) or (n mod 100=99) or (n mod 100=00) then writeln(g,'0');
end;
close(f);
close(g);
end.