题目描述

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

每次操作，你可以从 $n$ 中减去 $k$ 的任意次幂。具体来说，每次操作，你可以将 $n$ 替换为 $n - k^x$，其中 $x$ 为任意非负整数。

请你求出将 $n$ 变为 $0$ 所需的最少操作次数。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来每组测试用例占一行，每行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$）。

输出格式

对于每组测试用例，输出一个整数，表示将 $n$ 变为 $0$ 所需的最少操作次数，每个答案占一行。

说明/提示

在第一个测试用例中，$n = 5$，$k = 2$。我们可以按如下顺序进行操作：

1. 从 $5$ 中减去 $2^0 = 1$，此时 $n$ 变为 $5 - 1 = 4$。
2. 从 $4$ 中减去 $2^2 = 4$，此时 $n$ 变为 $4 - 4 = 0$。

可以证明，没有办法用少于 $2$ 次操作将 $n$ 变为 $0$，因此答案为 $2$。

在第二个测试用例中，$n = 3$，$k = 5$。我们可以按如下顺序进行操作：

1. 从 $3$ 中减去 $5^0 = 1$，此时 $n$ 变为 $3 - 1 = 2$。
2. 从 $2$ 中减去 $5^0 = 1$，此时 $n$ 变为 $2 - 1 = 1$。
3. 从 $1$ 中减去 $5^0 = 1$，此时 $n$ 变为 $1 - 1 = 0$。

可以证明，没有办法用少于 $3$ 次操作将 $n$ 变为 $0$，因此答案为 $3$。

由 ChatGPT 4.1 翻译

样例

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

2
3
1
4
21
10