Two players, A and B, are playing a stone-taking game. There is a pile of $n$ stones. Player A goes first, and they take turns removing stones from the pile. In the first turn, Player A can remove at most $k$ stones. In each subsequent turn, a player can remove at most twice the number of stones removed by the previous player. Each player must remove at least one stone per turn. The player who takes the last stone loses, and the other player wins. Given $k$, find the number of integers $n$ in the range $1$ to $N$ such that Player A has a winning strategy.

Input

The input consists of multiple test cases.

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

Each of the next $T$ lines contains two space-separated integers $k$ and $N$, representing a query.

Output

Output $T$ lines, each containing an integer representing the answer for the corresponding query in the order they were provided.

Examples

Input 1

3
1 5
2 5
1 10

Output 1

2
3
4

Note 1

When $k=1$:

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

Subtasks

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

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