Description

One day, Uncle Fang went to a game hosted by a mall. The mall arranged some staff members in a line. In front of each person, there are several piles of stones.

By coincidence, for the person at position $i$, the number of stones in the $j$-th pile is exactly the $j$-th digit of $i$ when written in base $K$. Now Uncle Fang is going to play a game: the mall will give him two integers $L, R$.

Uncle Fang needs to merge all the piles in front of each person whose position is in $[L, R]$ into a single pile. In each operation, he may choose two piles in front of one person and move some stones from one pile to the other. The cost is equal to (the number of stones moved) $\times$ (the distance moved).

The mall promises that as long as Uncle Fang completes the task, they will give him some coconuts; the smaller the cost, the more coconuts he will receive. So he is anxious and asks you to tell him the minimum cost. For example, for the person at position $12312$ in base $10$, the minimum cost to merge the stones is $1 \times 2 + 2 \times 1 + 3 \times 0 + 1 \times 1 + 2 \times 2 = 9$, that is, merge all stones into the third pile.

Input Format

The input consists of only $1$ line containing $3$ space-separated integers $L, R, K$, representing the two integers given by the mall and the base.

Output Format

Output only $1$ line containing $1$ integer, the minimum cost.

3 8 3

5

Hint

For $100\%$ of the testdata, $1 \le L \le R \le 10^{15}$, $2 \le K \le 20$.

Translated by ChatGPT 5