Вам заданы два числа \(n\) и \(k\).
За один шаг вы можете делать следующие действия:
Вам нужно посичтать минимальное количество шагов, необходимое для получения \(0\) из \(n\).
Первая строка содержит число \(t\) (\(1 \le t \le 100\)) — количество запросов.
Единственная строка каждого запроса содержит два числа \(n\) и \(k\) (\(1 \le n \le 10^{18}\), \(2 \le k \le 10^{18}\)).
Для каждого запроса выведите минимальное количество шагов для получения \(0\) из \(n\) в отдельной строке.
В первом тестовм примере необходимо выполнить следующую последовательность шагов: \(59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0\).
Во втором тестовом примере необходимо \(18\) раз разделить \(n\) на \(k\) а затем уменьшить \(n\) на \(1\).
2 59 3 1000000000000000000 10
8 19
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач