P2405 non's Balance Scale

non has been worried about his weight recently, and he wants to weigh himself. So, he found a balance scale and many weights.

The weights each have masses that are powers of $n$: $n^1, n^2, n^3, n^4, n^5$, and so on. non wants to know the minimum number of weights needed to measure his weight $m$. Note that weights can be placed on either the left or the right pan.

The first line contains a non-negative integer $m$, representing non's weight. The second line contains a positive integer $n$, representing the base of the powers for the weights.

Output a single integer representing the minimum number of weights required.

### Constraints For $30\%$ of the testdata, $m \le 2^{63} - 1$. For $100\%$ of the testdata, $0 \le m \le 10^{10000}$, $0 < n \le 10000$. Translated by ChatGPT 5