From Hero to Zero
Description
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.
Input
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}$).
Output
For each query print the minimum number of steps to reach $0$ from $n$ in single line.
Samples
2
59 3
1000000000000000000 10
8
19
Note
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$.