A12590. From Hero to Zero

You are given an integer $n$ and an integer $k$ .

In one step you can do one of the following moves:

- decrease $n$ by $1$ ;
- divide $n$ by $k$ if $n$ is divisible by $k$ .

For example, if $n = 27$ and $k = 3$ you can do the following steps: $27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$ .

You are asked to calculate the minimum number of steps to reach $0$ from $n$ .

The first line contains one integer $t$ ( $1 \le t \le 100$ ) — the number of queries.

The only line of each query contains two integers $n$ and $k$ ( $1 \le n \le 10^{18}$ , $2 \le k \le 10^{18}$ ).

For each query print the minimum number of steps to reach $0$ from $n$ in single line.

Steps for the first test case are: $59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$ .

In the second test case you have to divide $n$ by $k$ $18$ times and then decrease $n$ by $1$ .