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) }