Вам заданы два числа \(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\).
Выходные данные
Для каждого запроса выведите минимальное количество шагов для получения \(0\) из \(n\) в отдельной строке.
Примечание
В первом тестовм примере необходимо выполнить следующую последовательность шагов: \(59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0\).
Во втором тестовом примере необходимо \(18\) раз разделить \(n\) на \(k\) а затем уменьшить \(n\) на \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
59 3
1000000000000000000 10
|
8
19
|