给你两个整数 $$$n$$$ 和 $$$k$$$。
在一次运算中,您可以从 $$$n$$$ 中减去 $$$k$$$ 的任意幂。形式上,在一次操作中,对于任何非负整数 $$$x$$$,您可以将 $$$n$$$ 替换为 $$$(n-k^x)$$$。
求使 $$$n$$$ 等于 $$$0$$$ 所需的最少操作数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^9$$$)。
输出
对于每个测试用例,在新行中输出最小操作数。
示例
输入 #1
6 5 2 3 5 16 4 100 3 6492 10 10 1
输出 #1
2 3 1 4 21 10
注意
在第一个测试用例中,$$$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$$$ 就是答案。