Alligator Sky

There are $N$ balls in a box. You have two robots Alice and Bob. You will set favorite number for each of them. Both of their favorite numbers are positive integer, not exceeding $N$. Say, Alice’s favorite number is set as $A$ and Bob’s favorite number is set as $B$. Now, they move alternatingly. Alice moves first.

On Alice’s move, it takes exactly $A$ balls from the box. On Bob’s move, it takes exactly $B$ balls from the box. If someone cannot complete its move, the game stops.

You know your favorite integer is $K$ $(1 \le K \le N)$. That’s why, you will set the values of $A$ and $B$ in such a way that $A+B \ge K$ and the box will not contain any ball in the end. Remember both of $A$ and $B$ are positive integers, not exceeding $N$.

What is the maximum number of total moves the robots can perform, if you set the values of $A$ and $B$ satisfying the given conditions? It can be shown that there is at least one way of setting the values of $A$ and $B$ exists satisfying the given conditions.

Input

First line will have one integer $T$ $(1 \le T \le 10^5)$, denoting the number of testcases.

Each of the next $T$ lines will have two integers $N$ $(1 \le N \le 10^9)$ and $K$ $(1 \le K \le N)$, describing the testcase.

Output

Output one line for each testcase, consisting maximum possible number of total moves.

Sample

2
10 3
7 2

7
7

For first testcase, you can set $A=1$ and $B=2$. There will be $7$ moves in total.

Note that, if you set $A=2$ and $B=1$, after $6$ moves, there will be $1$ ball in the box. Alice cannot perform his move from here and the game ends. So, you cannot set $A=2$ and $B=1$ in this case.

You could set $A=10$ and $B=10$. That would result in $1$ total move. But it is not optimal here.