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.