Little F has a flashlight that requires two working batteries to function. He has many batteries, but some are dead. Specifically, there are $a$ working batteries and $b$ dead batteries. The only action he can take is to insert two batteries into the flashlight and observe whether it lights up. Given that he knows there are $a$ working batteries and $b$ dead batteries, he adopts an optimal strategy. He wants to know the minimum number of tests required to make the flashlight light up in the worst-case scenario.

Here is a simple example: suppose $a=2, b=1$. Let the batteries be numbered $1, 2, 3$. In the first test, he checks batteries $1$ and $2$, and the flashlight does not light up. In the second test, he checks batteries $1$ and $3$, and the flashlight does not light up. In the third test, he checks batteries $2$ and $3$, and the flashlight lights up. It can be proven that regardless of the strategy used, in the worst case, it takes three tests to make the flashlight light up.

Input

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

Each of the next $T$ lines contains two positive integers $a$ and $b$, representing the query for the minimum number of tests required in the worst case when there are $a$ working batteries and $b$ dead batteries. It is guaranteed that $a \ge 2$ and $b \ge 1$.

Output

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

Examples

Input 1

3
2 1
3 1
2 2

Output 1

3
2
6

Subtasks

For all data, it is guaranteed that $1 \le T \le 1000$, $2 \le a \le 1000$, and $1 \le b \le 1000$.

Subtask 1 ($10\%$): $a, b \le 4$.

Subtask 2 ($5\%$): $a = 2$.

Subtask 3 ($10\%$): $a = 3$.

Subtask 4 ($5\%$): $a > b + 1$.

Subtask 5 ($20\%$): $a, b \le 10$.

Subtask 6 ($30\%$): $a, b \le 30$.

Subtask 7 ($20\%$): $a, b \le 1000$.