Description

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.

Input Format

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 Format

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

99
10

2

Hint

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