Please read the new rule regarding the restriction on the use of AI tools. ×

A. Find Minimum Operations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$).

Output

For each test case, output the minimum number of operations on a new line.

Example
Input
6
5 2
3 5
16 4
100 3
6492 10
10 1
Output
2
3
1
4
21
10
Note

In the first test case, $$$n = 5$$$ and $$$k = 2$$$. We can perform the following sequence of operations:

  1. Subtract $$$2^0 = 1$$$ from $$$5$$$. The current value of $$$n$$$ becomes $$$5 - 1 = 4$$$.
  2. 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:

  1. Subtract $$$5^0 = 1$$$ from $$$3$$$. The current value of $$$n$$$ becomes $$$3 - 1 = 2$$$.
  2. Subtract $$$5^0 = 1$$$ from $$$2$$$. The current value of $$$n$$$ becomes $$$2 - 1 = 1$$$.
  3. 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.