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.

Note

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.

Find Minimum Operations

Examples