var fi,fo:text;
    i,j,n,t,k:longint;
    nrdiv,prim:array[1..1000000]of integer;
begin
     assign(fi,'divprim.in'); reset(fi);
     assign(fo,'divprim.out'); rewrite(fo);
     i:=3;
     while i<=500000 do
        begin
             j:=i;
             if prim[i]=0 then
                begin
                     nrdiv[i]:=1;
                     j:=j+i;
                     while j<=500000 do
                        begin
                             prim[j]:=1;
                             nrdiv[j]:=nrdiv[j]+1;
                             inc(j,i);
                        end;
                end;
             inc(i,2);
        end;
     readln(fi,t);
     for i:=1 to t do
        begin
             read(fi,n,k);
             for j:=n downto 1 do begin
             if j mod 2=0 then
                if nrdiv[j]+1=k then begin writeln(fo,j); break; end
                else else
                    if nrdiv[j]=k then begin writeln(fo,j); break; end;
                if j=1 then writeln(fo,'0');
             end;
        end;
     close(fi);
     close(fo);
end.