Последовательность

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

где s[i] = -1 or s[i] = 1, k[i] - целые, n должно быть минимизировано.

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

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

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

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

Примеры