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

Input

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

Output

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.

Note

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.