Розгляньмо натуральні числа та . Ваше завдання — представити число у вигляді алгебраїчної суми цілих степенів числа з найменшою можливою кількістю доданків. Тобто,

де s_i дорівнює або , k_i — цілі числа, а має бути мінімізовано.
Перший рядок містить натуральне число без провідних нулів. складається не більше ніж з цифр. Другий рядок містить ціле число (1 \le B \le 10^6).
Виведіть одне ціле число .
Приклад 1