342. Reihenfolge
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
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,
A =
s_{1} B^{k1} +
s_{2} B^{k2} +... +
s_{n} B^{kn}, where
s_{i} = 1 or
s_{i} = 1,
k_{i} are integers and
n should be minimized.
Input
The first line of the input 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
Print one integer number
n.
Example(s)
sample input

sample output

1120
10

4
