Problem Statement

The 3rd Green-or-Below Contest will be held in a classroom at the Aoyama Campus of Aoyama Gakuin University.

This classroom has long desks arranged in $10^{100}$ rows and $4$ columns. Each long desk has $2$ seats, and each chair can seat $1$ person (see the figure below).

Also, there are power outlets at both the left and right ends, and cords can be extended from the outlets to the long desks in the outermost columns.

Each contest participant brings their own computer, but some participants need to charge their computers.

Participants who need to charge their computers extend a cord from an outlet and connect it to their computers, so they must sit at a seat on a long desk in an outermost column.

Participants who do not need to charge their computers may sit at any seat.

There are $N$ participants who need to charge their computers and $M$ participants who do not.

Kushira-kun wants to seat the participants so that they are packed toward the front as much as possible.

When the participants are seated appropriately, what is the minimum possible value of "the maximum row number in which a participant is sitting"?

It is guaranteed by the constraints that all participants can sit in chairs.

Stated formally:

There is a sequence $A$ of length $N+M$. If the seat of the $i$-th $(1 \le i \le N+M)$ participant is on the long desk located in the $x$-th row from the top and the $y$-th column from the left, then $A_i = x$.

Find the minimum possible value of the maximum value of the sequence $A$.

Answer $T$ test cases.

Constraints

• $1 \le T \le 2 \times 10^5$
• $1 \le N,M \le 10^{9}$
• All input values are integers.

Input

The input is given from standard input in the following format.

$T$
$\text{test}_1$
$\text{test}_2$
$\vdots$
$\text{test}_T$

$\text{test}_i$ represents the $i$-th test case, and each test case is given in the following format.

$N\ M$

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1

Input

5
6 7
5 14
18 6
1 18
9 17

Output

2
3
5
3
4

For the $1$-st test case, by seating as follows, everyone can be seated within the first $2$ rows.
Yellow pentagons represent participants who need to charge their computers, and green circles represent participants who do not.

6
7764 52463
1658 7836
657456 647734
64567 734634
476 857467
48756587 675761

7529
1187
164364
99901
107243
12189147