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₁ B^k1 + s₂ B^k2 +... + s_n B^kn, where s_i = -1 or s_i = 1, k_i are integers and n should be minimized.

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⁶).

Print one integer number n.

sample input	sample output
1120 10	4