Problems
Reihenfolge
Reihenfolge
Consider positive integers A and B. Your task is to represent A as the algebraic sum of integer powers of B with the minimal possible number of terms. In other words,
where si
= -1 or si
= 1, ki
are integers and n should be minimized.
Input
The first line contains positive integer A written without leading zeroes. A contains no more than 3000 digits. Second line contains integer B (1 ≤ B ≤ 106
).
Output
Print one integer number n.
Input example #1
1120 10
Output example #1
4