Рабочее место участника

Once upon a time Baron Munchhausen traveled to the Moon. After that he often tells interesting stories about the Selenites. Recently Baron told us about their numeric system. They use a notation with negative radix!

Negative radix is quite hard for Humans, and even for Munchhausen. So, Baron did a trick to help himself on the Moon. He remembered all the numbers between 0 and `n` inclusively, which have the same notation for both Selenites’ negative radix `-k` and a more convenient positive radix `k`.

Munchhausen claims that he did that easily. But, you know, Baron can exaggerate a little. To catch him, you have to count how many numbers he must have remembered.

Note: the `k`-radix notation of a number `x` is a sequence of integers `a_0,\ a_1,\ …,\ a_p` such that `0\ ≤\ a_i\ <\ |k|` and `sum_{i=0}^p\ a_i\ *\ k^i\ =\ x`.

The single line of the input file contains two integer numbers `n` and `k` (`1\ ≤\ n\ ≤\ 10^15`, `2\ ≤\ k\ ≤\ 1\ 000`).

Output the number of numbers Baron Munchhausen must have remembered during his stay on the Moon.

21 3

9

21 2

8

In the first sample, Baron must have remembered numbers 0, 1, 2, 9, 10, 11, 18, 19 and 20.

For example, 19 has the same notation for both radix 3 and radix `-3`: `19\ =\ 201_3\ =\ 201_{-3}`, while 7 has not: `7\ =\ 21_3\ =\ 111_{-3}`.

In the second sample, the corresponding numbers are 0, 1, 4, 5, 16, 17, 20 and 21.