Description

Player A and Player B play a stone-taking game. There is a pile of $n$ stones. Player A moves first, and they take turns removing stones from the pile:

• On Player A's first move, the number of stones taken cannot exceed $k$.
• After that, on each move, the number of stones taken cannot exceed $2$ times the number taken by the previous player.
• Each player must take at least one stone each turn.

The player who takes the last stone loses, and the other player wins.

Given $k$, find how many integers $n$ in $[1, N]$ make Player A have a winning strategy in the game with $n$ stones.

Input Format

Multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain two integers $k$ and $N$ separated by a space, representing one query.

Output Format

Output $T$ lines. In the input order, each line contains one integer, the answer for that query.

3
1 5
2 5
1 10

2
3
4

Hint

Sample Explanation

For sample $1$, when $k=1$:

• If $n=1$, Player A can only take the only stone and thus loses.
• If $n=2$, Player A takes one stone, Player B must take the last stone, and Player A wins.
• If $n=3$, Player A can only take one stone, Player B then takes one stone, and Player A must take the last stone and thus loses.
• If $n=4$, Player A can only take one stone, Player B then takes two stones, and Player A must take the last stone and thus loses.
• If $n=5$, Player A can only take one stone. Player B can only take one or two stones, and Player A can always leave Player B the last stone, thus winning.

Data Notes and Hints

For all testdata, $1 \le T \le 10^5, k, N \le 10^{18}$.

• For $10\%$ of the testdata, $T, N \le 500$.
• For another $20\%$ of the testdata, $T, N \le 10^5$.
• For another $20\%$ of the testdata, $T \le 3, N \le 3 \times 10^6$.
• For another $20\%$ of the testdata, $k=1$.
• For the remaining $30\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5