Даны два целых числа \(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\)).
Для каждого набора входных данных выведите минимальное число операций на отдельной строке.
В первом наборе входных данных \(n = 5\) и \(k = 2\). Можно выполнить следующую последовательность операций:
Можно доказать, что невозможно сделать \(n\) равным \(0\) меньше чем за \(2\) операции. Значит, \(2\) и есть ответ на задачу.
Во втором наборе входных данных \(n = 3\) и \(k = 5\). Можно выполнить следующую последовательность операций:
Можно доказать, что невозможно сделать \(n\) равным \(0\) меньше чем за \(3\) операции. Значит, \(3\) и есть ответ на задачу.
6 5 2 3 5 16 4 100 3 6492 10 10 1
2 3 1 4 21 10
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач