One day, Uncle Fang went to participate in a game held at a mall. The mall had arranged some staff members in a row. Each person had several piles of stones in front of them. Coincidentally, the number of stones in the $j$-th pile in front of the person at position $i$ is exactly the $j$-th digit of $i$ when written in base $K$.

Now, Uncle Fang wants to play a game. The mall gives Uncle Fang two integers $L$ and $R$. Uncle Fang needs to merge all the stones of each person at positions in the range $[L, R]$ into a single pile.

In each operation, he can choose two piles of stones in front of a person and move some stones from one pile to the other. The cost is the number of stones moved multiplied by the distance moved.

The mall promises that as long as Uncle Fang completes the task, they will give him some coconuts; the lower the cost, the more coconuts he gets. Therefore, Uncle Fang is in a hurry and wants you to tell him the minimum cost.

For example: For a 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$ This means merging all stones into the third pile.

Input

The input consists of a single line containing three space-separated integers $L$, $R$, and $K$, representing the two integers given to Uncle Fang by the mall and the base $K$.

Output

The output consists of a single line containing one integer, representing the minimum cost.

Examples

Input 1

3 8 3

Output 1

5

Constraints

For $10\%$ of the data, $1 \le L \le R \le 10^5$

For $30\%$ of the data, $1 \le L \le R \le 10^7$

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