In a special 1-on-1 competition, the two sides use a "best of $n$ games" format, where $n$ is a given odd number. This means the competition lasts at most $n$ games, and the first player to win $\frac{n+1}{2}$ games is declared the winner, at which point the competition ends immediately.

Spectator A missed the live broadcast of this competition. Now that the competition has ended, spectator A knows that the competition lasted exactly $m$ games ($\frac{n+1}{2} \le m \le n$), but does not know the outcome of each game. Now A wants to watch the recording of this competition. A needs to watch the game recordings in order starting from the first game. Every time A finishes watching a game, they will know the winner of that game.

Please calculate the minimum number of games A needs to watch starting from the first game to ensure that they can determine the winner of the entire competition based on the outcomes of the games they have watched.

Input

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

Each of the following $T$ lines contains two positive integers $n$ and $m$, separated by a space, representing that the competition lasts at most $n$ games and that the competition lasted exactly $m$ games.

Data constraints: $1 \le n \le 10^9$, $n$ is an odd number, $\frac{n+1}{2} \le m \le n$, $1 \le T \le 10^4$.

Output

Output $T$ lines, each containing one integer, representing the corresponding answer.

Examples

Input 1

1
7 4

Output 1

1