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 = s1 Bk1 + s2 Bk2 +... + sn Bkn, where si = -1 or si = 1, ki 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 ≤ 106).

Output
Print one integer number n.

Example(s)
sample input
sample output
1120
10
4