P6791 [SNOI2020] Taking Stones.

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.

**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 $T$ lines. In the input order, each line contains one integer, the answer for that query.

#### 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