You are given two integers $$$n$$$ and $$$k$$$.
In one operation, you can subtract any power of $$$k$$$ from $$$n$$$. Formally, in one operation, you can replace $$$n$$$ by $$$(n-k^x)$$$ for any non-negative integer $$$x$$$.
Find the minimum number of operations required to make $$$n$$$ equal to $$$0$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$).
For each test case, output the minimum number of operations on a new line.
65 23 516 4100 36492 1010 1
2 3 1 4 21 10
In the first test case, $$$n = 5$$$ and $$$k = 2$$$. We can perform the following sequence of operations:
It can be shown that there is no way to make $$$n$$$ equal to $$$0$$$ in less than $$$2$$$ operations. Thus, $$$2$$$ is the answer.
In the second test case, $$$n = 3$$$ and $$$k = 5$$$. We can perform the following sequence of operations:
It can be shown that there is no way to make $$$n$$$ equal to $$$0$$$ in less than $$$3$$$ operations. Thus, $$$3$$$ is the answer.
Name |
---|