Statement

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

Format

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.

Sample

6
5 2
3 5
16 4
100 3
6492 10
10 1

2
3
1
4
21
10