Digit Sum in Base B

Given an unsigned integer N and a base B, compute the sum of digits of N when it is written in base B.

For example, 13 in base 2 is 1101, so the digit sum is 1 + 1 + 0 + 1 = 3.

Input

One line with two integers: N B.

• N is a positive integer and fits in uint
• $B \ge 2$

Output

One line with a single integer: the sum of the digits of N represented in base B.

Note: Input and output should all be in base 10.

Sample

Input

13 2

Output

3