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