Program divprim;
Var i,j:longint;
    x,t,max:longint;
    n,k:array[1..100000]of longint;
    h:array[0..2100000] of byte;
    sol:array[1..1000000,0..7] of longint;
    f,ff:text;
Begin
  sol[1,0]:=1;
  for i:=2 to 1000000 do
     if h[i]=0 then
       begin
        x:=0;
        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);
  max:=0;
  for i:=1 to t do
     begin
      readln(f,n[i],k[i]);
      if n[i]>max then max:=n[i];
     end;
  for i:=2 to max do
     begin
      sol[i]:=sol[i-1];
      sol[i,h[i]]:=i;
     end;
  for i:=1 to t do Writeln(ff,sol[n[i],k[i]]);
  close(ff);
  close(f);
End.