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−kx) 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≤t≤104). The description of the test cases follows.
The only line of each test case contains two integers n and k (1≤n,k≤109).
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 |
---|