Рассмотрим натуральные числа A и B. Вам следует представить число A в виде алгебраической суммы целочисленных степеней числа B с наименьшим количеством слагаемых. Другими словами,

где si = -1 or si = 1, ki - целые, n должно быть минимизировано.

Входные данные

Первая строка содержит натуральное число A без ведущих нулей. A содержит не более 3000 цифр. Вторая строка содержит целое число B (1 ≤ B ≤ 106).

Выходные данные

Вывести одно целое число n.