var p : array[1..1000000] of integer;
    t,i,j,n,k : longint;
    a : array[1..1000000,0..7] of longint;
    f,g : text;
begin
assign(f,'divprim.in');reset(f);
assign(g,'divprim.out');rewrite(g);
for i:=2 to 1000 do
  if p[i]=0 then
  begin
    j:=i;
    while j<=1000000 do
    begin
      inc(p[j]);
      inc(j,i);
    end;
  end;
for i:=2 to 1000000 do
  for j:=0 to 7 do
  begin
    a[i]:=a[i-1];
    a[i,p[i]]:=i;
  end;
read(f,t);
for i:=1 to t do
begin
  read(f,n,k);
  writeln(g,a[n,k]);
end;
close(g);
end.