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

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

Print one integer number n.

Examples