CF1175A From Hero to Zero

给定一个整数 $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$ 所需的最少步数。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示询问的组数。 每组询问包含一行，包含两个整数 $n$ 和 $k$（$1 \le n \le 10^{18}$，$2 \le k \le 10^{18}$）。

对于每组询问，输出一行一个整数，表示从 $n$ 变到 $0$ 所需的最少步数。

第一组样例的操作步骤为：$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$。 第二组样例中，你需要将 $n$ 除以 $k$ 共 $18$ 次，然后再将 $n$ 减 $1$。 由 ChatGPT 4.1 翻译