Count of B-Good Numbers

For a positive integer \(x\), let \(f(x,B)\) denote the digit sum of \(x\) in base \(B\). A positive integer \(p\) is called B-good if and only if for every positive integer \(q < p\), the inequality \(f(p,B) \ge f(q,B)\) holds.

Given positive integers \(n\) and \(B\), compute the number of positive integers \(\le n\) that are B-good.

Note: The digit sum \(f(x,B)\) of \(x\) in base \(B\) is defined as the sum of its digits when \(x\) is expressed in base \(B\).

inputFormat

The input consists of a single line containing two positive integers \(n\) and \(B\) separated by a space, where \(n\) is the upper limit and \(B\) is the base.

outputFormat

Output a single integer, which is the count of positive integers \(\le n\) that are B-good.

sample

10 10

9