D. Glass Bridge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$N$$$ players participating in a game involving a glass bridge. The bridge consists of $$$M$$$ steps, and each step has two glass panels: one is safe, and the other is fragile and will break if stepped upon.

The players cross the bridge one at a time, following their position in a queue from $$$1$$$ to $$$N$$$. The rules are as follows:

  • Players must cross the bridge in the sequence of their queue positions ($$$1, 2, \dots, N$$$).
  • Each step $$$i$$$ has one safe panel and one fragile panel.
  • When a player's turn comes, they start from step $$$1$$$ and move forward.
  • If a player reaches a step that was previously cleared by a predecessor, they simply step on the known safe panel and continue.
  • If a player reaches a step $$$i$$$ that has not been successfully crossed yet:
    • They must choose one of the two panels.
    • If they choose the fragile panel, they are eliminated. Their turn ends, and the next player in the queue begins their attempt from step $$$1$$$, now knowing which panel at step $$$i$$$ is the safe one.
    • If they choose the safe panel, they proceed to step $$$i+1$$$.
  • The game ends immediately when a player successfully lands on the safe panel of the $$$M$$$-th step. That player is the sole winner.

Every player is rational and will use all information revealed by previous players. If a player reaches a step where the safe panel is unknown, they will choose one of the two panels with a $$$50\%$$$ probability of success.

You have the chance to bribe the organizers to pick any starting position from $$$1$$$ to $$$N$$$. Your goal is to choose the position $$$k$$$ that maximizes your probability of being the sole winner. If multiple positions yield the same maximum probability, choose any such $$$k$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

Each test case consists of a single line containing two integers:

  • $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — total number of players.
  • $$$M$$$ ($$$1 \le M \le 2 \cdot 10^5$$$) — number of steps on the bridge.
Output

For each test case, output a single integer — the optimal position $$$k$$$ ($$$1 \le k \le N$$$) to maximize your winning probability.

Example
Input
3
1 1
2 2
3 3
Output
1
2
3
Note

The following diagram illustrates the glass bridge for the second test case:

For the second test case, if you start at position $$$1$$$ in the queue, then you must correctly choose the safe panel on both steps. Since each unknown step has a success probability of $$$1/2$$$, your probability of winning is:

$$$$$$ \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} = 25\%. $$$$$$

However, if you start at position $$$2$$$, there are two cases where you win:

  • The first player fails on the first step with probability $$$1/2$$$. In this case, the safe panel of the first step becomes known, and you only need to correctly guess the second step. Therefore, your probability of winning in this scenario is: $$$$$$ \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}. $$$$$$

  • The first player successfully crosses the first step and then fails on the second step with probability: $$$$$$ \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}. $$$$$$ In this case, both safe panels become known, so you win with probability $$$1$$$. Therefore, your probability of winning in this scenario is: $$$$$$ \frac{1}{4} \times 1 = \frac{1}{4}. $$$$$$

Hence, the total probability of winning when starting at position $$$2$$$ is:

$$$$$$ \frac{1}{4} + \frac{1}{4} = \frac{1}{2} = 50\%. $$$$$$