type matrix=array[0..10,0..10]of byte;
     sor =array[0..10]of byte;

var a:matrix;
    b:sor;
    i,j,n,m,x:integer;
    f,g:text;

begin
a[0,1]:=0;
a[1,1]:=1;
b[0]:=1;
b[1]:=1;

for i:=2 to 9 do begin

j:=0;
x:=i;
while a[i,1]<>x mod 10 do begin
                        inc(j);
                        a[i,j]:=x mod 10;
                        x:=x*i;
                        end;
b[i]:=j;
end;


assign(f,'cifra.in');reset(f);
assign(g,'cifra.out');rewrite(g);

readln(f,n);
for i:=1 to n do begin
                 readln(f,x);
                 m:=x mod 10;
                 x:=x mod b[m];
                 writeln(g,a[m,x]);
                 end;



close(f);
close(g);

end.