gets.to_i.times {
  j, k = gets.split.map(&:to_i)
  if k == 1 then
    puts j-1
    next
  end
  f, a, ck = 1, 1, k
  while f < j do
    f += ck
    a += 1
    ck *= k
  end
  puts (a-1)
}