위대한 사기꾼

믿기 힘들겠지만 상근이는 이번 겨울 방학에 달에 갔다 왔다. 방학이 끝나고 다시 학교로 돌아온 상근이는 친구들에게 달나라 사람(Selenites)을 만났던 이야기를 해주었다.

상근이는 달에서 사용하는 수 체계를 주로 설명해주었다. 달에서는 음의 진법을 사용한다.

음의 진법은 사람들이 이해하기는 어렵다. 따라서, 상근이는 달을 여행하는 동안 0과 \(n\)을 포함하는 사이의 수 중에서 \(k\)진법과 \(-k\)진법에서 표현이 같은 수를 모두 외웠다. 상근이가 외운 숫자의 개수를 구하는 프로그램을 작성하시오.

\(x\)의 \(k\)진법 표현은 0 ≤ \(a_i\) < \(\left| k  \right| \), \(\sum_{i = 0} ^ {p} {a_i \times k^i} = x\)를 만족하는 수열 \(a_0\),\(a_1\),...,\(a_p\)이다.

첫째 줄에 \(n\)과 \(k\)가 주어진다. (1 ≤ \(n\) ≤ 1015, 2 ≤ \(k\) ≤ 1,000)

첫째 줄에 상근이가 달에서 생활하면서 외운 숫자의 개수를 출력한다.

첫 번째 예제에서 상근이는 0, 1, 2, 9, 10, 11, 18, 19, 20을 외웠다.

19는 3진법과 -3진법에서 19 = 2013 = 201-3 으로 표현이 같다. 하지만, 7은 7 = 213 = 111-3 으로 같지 않다.

두 번째 예제의 경우에는 0, 1, 4, 5, 16, 17, 20, 21을 외우면 된다.