CF1870F.Lazy Numbers

You are given positive integers $n$ and $k$. For each number from $1$ to $n$, we write its representation in the number system with base $k$ (without leading zeros) and then sort the resulting array in lexicographic order as strings. In the sorted array, we number the elements from $1$ to $n$ (i.e., indexing starts from $1$). Find the number of values $i$ such that the representation of number $i$ is at the $i$-th position in the sorted array of representations.

Examples of representations: $1$ in any number system is equal to $1$, $7$ with $k = 3$ is written as $21$, and $81$ with $k = 9$ is written as $100$.

给定正整数 $n$ 和 $k$。对从 $1$ 到 $n$ 的每个数，我们将其写成以 $k$ 为底的进制表示（不带前导零），然后将得到的所有字符串按字典序排序。在排序后的数组中，我们对元素编号为 $1$ 到 $n$（即下标从 $1$ 开始）。求满足“数字 $i$ 的进制表示恰好位于排序后数组的第 $i$ 个位置”的 $i$ 的个数。

进制表示示例：任意进制下 $1$ 的表示均为 $1$；当 $k = 3$ 时，$7$ 的表示为 $21$；当 $k = 9$ 时，$81$ 的表示为 $100$。

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. This is followed by a description of the test cases.

The only line of each test case contains integers $n$ and $k$ ($1 \leq n \leq 10^{18}$, $2 \leq k \leq 10^{18}$).

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{18}$，$2 \leq k \leq 10^{18}$）。

For each test case, output a single integer — the number of values $1 \leq i \leq n$ such that the representation of number $i$ in the number system with base $k$ is at the $i$-th position after sorting.

对于每个测试用例，输出一个整数——满足条件的 $1 \leq i \leq n$ 的个数：即数字 $i$ 在 $k$ 进制下的表示，在所有 $1$ 到 $n$ 的数字的 $k$ 进制表示按字典序（或数值序？需结合上下文）排序后，恰好位于第 $i$ 个位置。

In the first test case, for numbers $1$ and $2$, their representations are at positions $1$ and $2$ respectively.

In the second test case, the sorted array is $[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$, and only the representations of numbers $1$ and $2$ are at the required positions.

In the third test case, the sorted array is $[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$, and only the number $1$ is at its position.

在第一个测试用例中，数字 $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$ 位于其对应的位置上。