A. Минимальное число операций
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых числа $$$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$$$).

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

Для каждого набора входных данных выведите минимальное число операций на отдельной строке.

Пример
Входные данные
6
5 2
3 5
16 4
100 3
6492 10
10 1
Выходные данные
2
3
1
4
21
10
Примечание

В первом наборе входных данных $$$n = 5$$$ и $$$k = 2$$$. Можно выполнить следующую последовательность операций:

  1. Вычесть $$$2^0 = 1$$$ из $$$5$$$. После этого $$$n$$$ принимает значение $$$5 - 1 = 4$$$.
  2. Вычесть $$$2^2 = 4$$$ из $$$4$$$. После этого $$$n$$$ принимает значение $$$4 - 4 = 0$$$.

Можно доказать, что невозможно сделать $$$n$$$ равным $$$0$$$ меньше чем за $$$2$$$ операции. Значит, $$$2$$$ и есть ответ на задачу.

Во втором наборе входных данных $$$n = 3$$$ и $$$k = 5$$$. Можно выполнить следующую последовательность операций:

  1. Вычесть $$$5^0 = 1$$$ из $$$3$$$. После этого $$$n$$$ принимает значение $$$3 - 1 = 2$$$.
  2. Вычесть $$$5^0 = 1$$$ из $$$2$$$. После этого $$$n$$$ принимает значение $$$2 - 1 = 1$$$.
  3. Вычесть $$$5^0 = 1$$$ из $$$1$$$. После этого $$$n$$$ принимает значение $$$1 - 1 = 0$$$.

Можно доказать, что невозможно сделать $$$n$$$ равным $$$0$$$ меньше чем за $$$3$$$ операции. Значит, $$$3$$$ и есть ответ на задачу.