program j01;
const maxn=1000086;
var f,l:array[0..maxn]of longint;
    time,x,k,t,i,head,tail:longint;
begin
  readln(time);
  while time>0 do
  begin
    dec(time);
    readln(x,k,t);
    f[x]:=0;
    l[1]:=x;
    head:=1;tail:=1;
    for i:=x-1 downto 1 do
    begin
      while (l[head]-t>i)and(head<tail) do inc(head);
      if (i*k<=x)and(i*k>i) then
      begin
        if f[i*k]<f[l[head]] then f[i]:=f[i*k]+1 else f[i]:=f[l[head]]+1
      end else f[i]:=f[l[head]]+1;
      while (tail>=head)and(f[l[tail]]>f[i]) do dec(tail);
      inc(tail);l[tail]:=i;
    end;
    writeln(f[1]);
  end;
end.