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

Вам заданы два числа $$$n$$$ и $$$k$$$.

За один шаг вы можете делать следующие действия:

  • уменьшить $$$n$$$ на $$$1$$$;
  • разделить $$$n$$$ на $$$k$$$ если $$$n$$$ делится $$$k$$$.
Например, если $$$n = 27$$$ и $$$k = 3$$$ Вы можете совершить следующую последовательность шагов: $$$27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

Вам нужно посичтать минимальное количество шагов, необходимое для получения $$$0$$$ из $$$n$$$.

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

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 100$$$) — количество запросов.

Единственная строка каждого запроса содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{18}$$$).

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

Для каждого запроса выведите минимальное количество шагов для получения $$$0$$$ из $$$n$$$ в отдельной строке.

Пример
Входные данные
2
59 3
1000000000000000000 10
Выходные данные
8
19
Примечание

В первом тестовм примере необходимо выполнить следующую последовательность шагов: $$$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

Во втором тестовом примере необходимо $$$18$$$ раз разделить $$$n$$$ на $$$k$$$ а затем уменьшить $$$n$$$ на $$$1$$$.