A. 求最少操作次数

每个测试的时间限制：1 秒
内存限制：256 兆字节

题目描述

给你两个整数 $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$）。

输出格式

对于每个测试用例，在新的一行输出最少操作次数。

输入样例

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

输出样例

2
3
1
4
21
10

样例解释

第一个测试用例：$n = 5$，$k = 2$。我们可以执行以下操作序列：

1. 减去 $2^0 = 1$，$n$ 变为 $5 - 1 = 4$；
2. 减去 $2^2 = 4$，$n$ 变为 $4 - 4 = 0$。

可以证明无法在少于 $2$ 次操作内使 $n$ 变为 $0$，因此答案为 $2$。

第二个测试用例：$n = 3$，$k = 5$。我们可以执行以下操作序列：

1. 减去 $5^0 = 1$，$n$ 变为 $3 - 1 = 2$；
2. 减去 $5^0 = 1$，$n$ 变为 $2 - 1 = 1$；
3. 减去 $5^0 = 1$，$n$ 变为 $1 - 1 = 0$。

可以证明无法在少于 $3$ 次操作内使 $n$ 变为 $0$，因此答案为 $3$。