题号：NC54488
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
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 a0, a1, …, ap such that 0 ≤ ai < |k| and 
∑p i=0 ai· ki = x.
输入描述:
The single line of the input file contains two integer numbers n and k (1 ≤ n ≤ 1015, 2 ≤ k ≤ 1 000).
输出描述:
Output the number of numbers Baron Munchhausen must have remembered during his stay on the Moon.
示例1