CF1870F Lazy Numbers

给定正整数 $n$ 和 $k$。对于每个从 $1$ 到 $n$ 的数字，将其用 $k$ 进制表示（不含前导零），然后将所有表示按字典序作为字符串排序。在排序后的数组中，将元素从 $1$ 到 $n$ 编号（即编号从 $1$ 开始）。求有多少个 $i$ 满足数字 $i$ 的 $k$ 进制表示在排序后的数组中正好处于第 $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$ 和 $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$ 处于其位置。 由 ChatGPT 4.1 翻译