Upon arrival, Vasily and Peter found a strange device in their hotel room. It was equipped with a display that showed the number 0, and two buttons. Vasily immediately realized that the first button increases the number on the display by 1, and the second multiplies it by K. At that moment Peter found a piece of paper on his bed, on which the single number N was written.
Now the friends want to reproduce the number N on the display of the device they found, and because there is still a lot of things to do, they are interested in the minimum number of presses on the device's buttons to get the number N.
Input
The first line of the input contains a non-negative integer N (1 ≤ N ≤ 10
9 ).
The second line of the input contains a positive integer K (2 ≤ K ≤ 10
9 ).
Imprint
Print a single number — the minimum number of presses on the device's buttons to receive the number N on its display.
Examples
Remark
In the example from the condition, Vasily and Peter want to reproduce the number 4. The button multiplies by 2 the number that is shown on the display. In the first operation, the friends increase the current number by 1 by pressing the first button, after which it becomes 1. Then they multiply it by 2 by pressing the second button. The current number becomes 2. After that, to get the number 4 on the display, it is enough to press the second button once and multiply the current number (that is, 2) by 2. It is easy to show that it is impossible to get the number 4 in less than three operations. Thus, the minimum number of actions is three.