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

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

def calc(n, k)
    k == 1 ? (n-1) : calc_dfs(n, k)
end

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