program pascal;
var f,g:text; n,i,j,k,nr,t:longint;
    v:array[1..1000000] of 0..1;
    x:array[1..1000000] of 0..7;
    ok:boolean;

    procedure formare;
    begin
      n:=1000000;
      for i:=2 to trunc(sqrt(n)) do
      if v[i]=0 then
        begin
        inc(x[i]);
        for j:=2 to (n div i) do
                begin
                v[i*j]:=1;
                inc(x[i*j]);
                end;
        end;

      x[1]:=0;
      for i:=2 to n do
      if x[i]=0 then x[i]:=1;
    end;

begin
assign(f,'divprim.in'); reset(f);
assign(g,'divprim.out'); rewrite(g);
formare;
readln(f,t);
for nr:=1 to t do
 begin
   readln(f,n,k);
   ok:=false;
   for i:=n downto 1 do
   if x[i]=k then
            begin
               writeln(g,i);
               ok:=true;
               break;
            end;
   if not ok then writeln(g,0);
  end;

close(f);
close(g);
end.