Alligator Sky

Limits 1s, 256 MB

There are NN 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 NN. Say, Alice’s favorite number is set as AA and Bob’s favorite number is set as BB. Now, they move alternatingly. Alice moves first.

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

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

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


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

Each of the next TT lines will have two integers NN (1N109)(1 \le N \le 10^9) and KK (1KN)(1 \le K \le N), describing the testcase.


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


10 3
7 2

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

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

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