program gaju;
var s:array[1..100000,0..7]of longint;
    v:array[1..100000]of longint;
    i,h,j,k,n,t:integer;
    f,g:text;
begin
assign(f,'divprim.in');reset(f);
assign(g,'divprim.out');rewrite(g);
readln(f,t);
for h:=1 to t do begin
readln(f,n,k);
fillchar(v,sizeof(v),0);
i:=2;
while i<=n do begin
      if v[i]=0 then begin
         v[i]:=1;
         j:=2*i;
         while j<=n do begin
               v[j]:=v[j]+1;
               j:=j+i;
         end;end;
      i:=i+1;
end;
for i:=3 to n do begin
    for j:=0 to k do s[i,j]:=s[i-1,j];
    s[i,v[i]]:=i;
    end;
writeln(g,s[n,k]);
end;
close(g);
end.