给定正整数 $$$n$$$ 和 $$$k$$$。对于从 $$$1$$$ 到 $$$n$$$ 的每个数字,我们以 $$$k$$$ 为基数(不带前导零)编写其在数字系统中的表示形式,然后按字典顺序将结果数组排序为字符串。在排序后的数组中,我们对元素进行编号,从 $$$1$$$ 到 $$$n$$$ (即索引从 $$$1$$$ 开始)。查找值 $$$i$$$ 的数量,使得数字 $$$i$$$ 的表示位于表示排序数组中的第 $$$i$$$ 个位置。
表示示例:任何数系中的 $$$1$$$ 都等于 $$$1$$$,$$$7$$$ 与 $$$k = 3$$$ 写为 $$$21$$$,$$$81$$$ 与 $$$k = 9$$$ 写为 $$$100$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例的唯一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq k \leq 10^{18}$$$)。
输出
对于每个测试用例,输出一个整数 - 值的数量 $$$1 \leq i \leq n$$$,使得数字 $$$i$$$ 在以 $$$k$$$ 为基数的数字系统中的表示形式在排序后位于第 $$$i$$$ 位置。
示例
输入 #1
8 2 2 4 2 6 4 33 2 532 13 780011804570805480 3788 366364720306464627 4702032149561577 293940402103595405 2
输出 #1
2 2 1 3 1 3789 1 7
注意
在第一个测试用例中,对于数字 $$$1$$$ 和 $$$2$$$,它们的表示分别位于位置 $$$1$$$ 和 $$$2$$$ 处。
在第二个测试用例中,排序后的数组为 $$$[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$$$,并且只有数字 $$$1$$$ 和 $$$2$$$ 的表示位于所需位置。
在第三个测试用例中,排序后的数组为 $$$[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$$$,只有数字 $$$1$$$ 位于其位置。