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

给你两个整数 $n$ 和 $k$。

每一步你可以执行以下操作之一：

• 将 $n$ 减 $1$；
• 若 $n$ 能被 $k$ 整除，则将 $n$ 除以 $k$。

例如，当 $n = 27$ 且 $k = 3$ 时，你可以执行如下步骤：$27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$。

你需要计算从 $n$ 到达 $0$ 所需的最少步数。

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

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 查询次数。

每个查询仅一行，包含两个整数 $n$ 和 $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.

对于每个查询，在单独一行中输出从 $n$ 到达 $0$ 所需的最少步数。

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

第一个测试用例的步骤为：$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$。

在第二个测试用例中，你需要将 $n$ 除以 $k$ 共 $18$ 次，然后将 $n$ 减 $1$。