var f,g:text;
    i,t:longint;
    c1,c2:char;

procedure vizsgal(c1,c2:char);
var szj1,szj2,szam:byte;
    kod:integer;
begin
 val(c1,szj1,kod);  val(c2,szj2,kod);
 szam:=szj1*10+szj2;
 if (szj2 in [0,1,5,6,9]) or ((szj2 in [3,7])and(szam mod 4=1)) then writeln(g,szj2)
 else if ((szj2 in [2,8])and(szam mod 4=2)) then writeln(g,4)
    else if ((szj2 in [2,8])and(szam mod 4=0))or(szj2=4) then writeln(g,6)
        else if ((szj2=3)and(szam mod 4=3)) then writeln(g,7)
            else if ((szj2=7)and(szam mod 4=3)) then writeln(g,3)
end;

begin
assign(f,'cifra.in');
assign(g,'cifra.out');
reset(f);
rewrite(g);
 readln(f,t);
 for i:=1 to t do begin
   read(f,c2);c1:='0';     {csak az utolso ket szj-re van szukseg}
   while not eoln(f) do begin
     c1:=c2;
     read(f,c2);
   end;
   vizsgal(c1,c2); {beirja a megfelelo szamjegyet}
   readln(f);
 end;
close(f);
close(g);
end.