var f,g:text;
    t,n,k,i,j,iesit:longint;
    v:array[2..1000000] of longint;

procedure ciur;
var i,j:longint;
begin
  fillchar(v,sizeof(v),0);
  for i:=2 to 500000 do
    begin
      if v[i]=0 then
        begin
          v[i]:=1;
          j:=2;
          while j*i<=1000000 do
            begin
              inc(v[j*i]);
              inc(j);
            end;
        end;
    end;
end;

begin
  assign(f,'divprim.in');
  assign(g,'divprim.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  ciur;
  for i:=1 to t do
    begin
      readln(f,n,k);
      iesit:=0;
      for j:=n downto 2 do
        begin
          if v[j]=0 then
            v[j]:=1;
          if v[j]=k then
            begin
              writeln(g,j);
              iesit:=1;
              break;
            end;
        end;
      if iesit=0 then
        writeln(g,'0');
    end;
  close(f);
  close(g);
end.