q = gets.to_i
q.times {
    n, k = gets.chomp.split.map &:to_f

    d = if k == 1
        (n - 1)
    else
        d = ( Math.log( n * (k - 1) + 1 ) / Math.log(k)  - 1 ).ceil
    end

    p d.to_i
}