Даны два целых числа $$$n$$$ и $$$k$$$.
За одну операцию вы можете вычесть из $$$n$$$ любую степень $$$k$$$. Формально, за одну операцию вы можете заменить $$$n$$$ на $$$(n-k^x)$$$ для любого неотрицательного целого числа $$$x$$$.
Найдите минимальное число операций, необходимое, чтобы сделать $$$n$$$ равным $$$0$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 10^9$$$).
Для каждого набора входных данных выведите минимальное число операций на отдельной строке.
65 23 516 4100 36492 1010 1
2 3 1 4 21 10
В первом наборе входных данных $$$n = 5$$$ и $$$k = 2$$$. Можно выполнить следующую последовательность операций:
Можно доказать, что невозможно сделать $$$n$$$ равным $$$0$$$ меньше чем за $$$2$$$ операции. Значит, $$$2$$$ и есть ответ на задачу.
Во втором наборе входных данных $$$n = 3$$$ и $$$k = 5$$$. Можно выполнить следующую последовательность операций:
Можно доказать, что невозможно сделать $$$n$$$ равным $$$0$$$ меньше чем за $$$3$$$ операции. Значит, $$$3$$$ и есть ответ на задачу.
Название |
---|