Program divprim;
Var i,j:longint;
    x,t,n,k:longint;
    h:array[0..1100000] of byte;
    f,ff:text;
Begin
  for i:=2 to 100000 do
     if h[i]=0 then
       begin
        x:=i;
        repeat
         x:=x+i;
         if h[x]<=7 then inc(h[x]);
         if h[x]>7 then h[x]:=200
        until(x>=1000000);
       end;

  assign(f,'divprim.in');
  reset(f);
  assign(ff,'divprim.out');
  rewrite(ff);
  readln(f,t);
  for i:=1 to t do
     begin
      readln(f,n,k);
      j:=n+1;
      repeat
       j:=j-1;
      until((j=0) or (h[j]=k));
      Writeln(ff,j);
     end;
  close(ff);
  close(f);
End.