Шоніко пропонує Лоціко віднайти мінімальну кількість оперецій, щоб натуральне число \(\bf{n}\) перетворити в нуль віднімаючи від нього деяку степінь натурального числа \(\bf{k}\). І Шоніко наводить такий приклад нехай \(\bf{n = 10}, \bf{k = 2}\). Якщо від \(\bf{10}\) віднімемо \(\bf {8 = 2^3}\), а потім \(\bf{2 = 2^1}\), то отримаємо \(\bf{0}\), отже мінімальна кількість операцій становитиме 2

Input Specification

У єдиному рядку записані два натуральні числа \(n\) i \(k\) \((k \le n \le 10^{18})\)

Output Specification

У вихідний потік виведіть відповідь на задачу - мінімальну кількість операцій, яку необхідно застосувати, щоб задане число перетворити у нуль.

Sample Input 1

10 2

Sample Output 1

2