program fainnaspa;
var v:array[1..1000010]of integer;
    f,g:text;
    i,n,k,t:longint;

    procedure rez;
var i,j:longint;
begin
fillchar(v,n,0);
i:=2;
while (i<=n) do begin
      if v[i]=0 then begin
         j:=i*2;
      while (j<=n) do begin
                inc(v[j]);
                j:=j+i;
      end;
      end;
     i:=i+1;
end;
for i:=n downto 2 do if v[i]=k then begin
         writeln(g,i);
         break;
         end
         else if i=2 then writeln(g,0);
end;

begin
assign(f,'divprim.in');reset(f);
assign(g,'divprim.out');rewrite(g);
readln(f,t);
for i:=1 to t do begin
         readln(f,n,k);
         rez;
end;
close(f);close(g);
end.