var f,g:text;
    t,n,k,i,j,iesit:longint;
    v:array[2..1000000] of longint;
    cate:array[0..7] of longint=(0,2,6,30,210,2310,30030,510510);
procedure ciur;
var i,j:longint;
begin
  fillchar(v,sizeof(v),0);
  for i:=2 to 499979 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;
      if (k=7) then begin
        if n=510510 then begin
          writeln(g,n);
          iesit:=1;
          end;
        end
      else
      for j:=n downto cate[k] 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.