program pascal;
var f,g:text; n,i,j,k,t,l:longint;
    v:array[1..1000000] of longint;
    x:array[1..1000000] of longint;
    a:array[0..7,1..1000000] of longint;
    ok:boolean;

procedure form;
begin
 n:=1000000;
   for i:=2 to trunc(sqrt(n)) do
   if v[i]=0 then
   begin
    for j:=2 to (n div i) do
               begin
               v[i*j]:=1;
               inc(x[i*j]);
               end;
   end;

  a[0,1]:=0;
end;

begin
assign(f,'divprim.in'); reset(f);
assign(g,'divprim.out'); rewrite(g);
form;
for i:=2 to n do
  begin
  if x[i]=0 then
           begin
             x[i]:=1;
             a[1,i]:=i;
           end;
  for j:=1 to 7 do a[j,i]:=a[j,i-1];
  a[x[i],i]:=i;
  end;

readln(f,t);
for i:=1 to t do
 begin
   read(f,l,k);
   writeln(g,a[k,l]);
 end;

close(f);
close(g);
end.