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