You are given a starting number ~t~ and an exponentiation base ~b~.

Your goal is to reduce ~t~ to exactly ~0~ using as few operations as possible.

In a single operation, you may subtract any integer power of ~b~ with a non-negative exponent. In other words, you may choose any integer ~x \geq 0~ and perform:

$$\displaystyle t := t - b^x $$

You may only perform an operation if the resulting value of ~t~ is non-negative.

Determine the minimum number of operations required to reduce ~t~ to ~0~.

Input

The input consists of a single line containing two integers ~t~ (~0 \leq t \leq 2^{31}~) and ~b~ (~1 \leq b \leq 2^{31}~). ~t~ represents the starting number, and ~b~ represents the base used for exponentiation.

Output

Output a single integer representing the minimum number of operations required to reduce ~t~ to ~0~.

Examples

Input 1

10 2

Output 1

2

We can reduce ~10~ to ~0~ in two operations:

• ~10-2^3=2~
• ~2-2^1=0~

There is no shorter sequence of operations.

Input 2

7 2

Output 2

3

We can reduce ~7~ to ~0~ in three operations:

• ~7-2^2=3~
• ~3-2^1=1~
• ~1-2^0=0~

There is no shorter sequence of operations.