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$ .

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}$ ).

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.

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.