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 s[i]
= -1 or s[i]
= 1, k[i]
are integers and n should be minimized.
Input data
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 ≤ 10^6
).
Output data
Print one integer number n.
Examples
Input example #1
1120 10
Output example #1
4