eolymp
bolt
Try our new interface for solving problems
Problems

Reihenfolge

Reihenfolge

Time limit 1 second
Memory limit 128 MiB

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,

prb8500.gif

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 (1B10^6).

Output data

Print one integer number n.

Examples

Input example #1
1120
10
Output example #1
4
Source 2007 Петрозаводск, Saratov for Karelia with love, Январь 28, Задача G