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. In the first test case, (n = 5) and (k = 2). We can perform the following sequence of operations: Subtract (2^0 = 1) from (5). The current value of (n) becomes (5 - 1 = 4). Subtract (2^2 = 4) from (4). The current value of (n) becomes (4 - 4 = 0). 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: Subtract (5^0 = 1) from (3). The current value of (n) becomes (3 - 1 = 2). Subtract (5^0 = 1) from (2). The current value of (n) becomes (2 - 1 = 1). Subtract (5^0 = 1) from (1). The current value of (n) becomes (1 - 1 = 0). 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.