def lscan; gets.split.map(&:to_i); end

def calc(n, k)
    n <= 0 ? 0 : 1 + calc((n-1)/k, k) 
end

gets.to_i.times do
    n, k = lscan
    p calc(n-1, k)
end