Даны два целых числа \(n\) и \(k\).
За одну операцию вы можете вычесть из \(n\) любую степень \(k\). Формально, за одну операцию вы можете заменить \(n\) на \((n-k^x)\) для любого неотрицательного целого числа \(x\).
Найдите минимальное число операций, необходимое, чтобы сделать \(n\) равным \(0\).
Выходные данные
Для каждого набора входных данных выведите минимальное число операций на отдельной строке.
Примечание
В первом наборе входных данных \(n = 5\) и \(k = 2\). Можно выполнить следующую последовательность операций:
- Вычесть \(2^0 = 1\) из \(5\). После этого \(n\) принимает значение \(5 - 1 = 4\).
- Вычесть \(2^2 = 4\) из \(4\). После этого \(n\) принимает значение \(4 - 4 = 0\).
Можно доказать, что невозможно сделать \(n\) равным \(0\) меньше чем за \(2\) операции. Значит, \(2\) и есть ответ на задачу.
Во втором наборе входных данных \(n = 3\) и \(k = 5\). Можно выполнить следующую последовательность операций:
- Вычесть \(5^0 = 1\) из \(3\). После этого \(n\) принимает значение \(3 - 1 = 2\).
- Вычесть \(5^0 = 1\) из \(2\). После этого \(n\) принимает значение \(2 - 1 = 1\).
- Вычесть \(5^0 = 1\) из \(1\). После этого \(n\) принимает значение \(1 - 1 = 0\).
Можно доказать, что невозможно сделать \(n\) равным \(0\) меньше чем за \(3\) операции. Значит, \(3\) и есть ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 2
3 5
16 4
100 3
6492 10
10 1
|
2
3
1
4
21
10
|