var f,g:Text;
    a:array[0..10,0..1000010]of longint;
    v:array[0..1000010]of longint;
    t,i,j,n,k,ok:longint;
begin
assign(f,'divprim.in');
assign(g,'divprim.out');
reset(f);
rewrite(G);
read(f,t);
for i:=1 to 500000 do
  v[i*2]:=1;
i:=3;
while (i<1000000) do
  begin
    if (v[i]=0)then
      for j:=1 to 1000000 div i do
        inc(v[i*j]);
    inc(i,2);
  end;
for i:=1 to 7 do
  begin
    a[i,1]:=0;
    for j:=2 to 10000 do
      if (v[j]=i)then a[i,j]:=j else a[i,j]:=a[i,j-1];
  end;
for i:=1 to t do
  begin
    read(f,n,k);
    if (k=0)then writeln(g,1)else writeln(g,a[k,n]);
  end;
close(F);
close(g);
end.