给你一个整数 $$$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$$$ 的最小步骤数。
示例
输入 #1
2 59 3 1000000000000000000 10
输出 #1
8 19
注意
第一个测试用例的步骤是:$$$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$。
在第二个测试用例中,您必须将 $$$n$$$ 除以 $$$k$$$ $$$18$$$ 次,然后将 $$$n$$$ 减去 $$$1$$$。