Walk_alone is anxious to prepare for a programming contest, and he has ideas for  problems now. Preparing a problem from scratch requires two jobs: making and validating. He asked  people to help him with these two jobs. 

All these  people are skilled at making and validating problems, and each person needs exactly  hour to do one of these two jobs. A job should be done by only one person without interruption (but making and validating one problem can be done by two different people), and a problem must be made before validated. Now Walk_alone wants to know the minimum hours to prepare for the contest if he arranges everyone's job properly.

The input contains multiple test cases.

The first line of the input contains an integer  indicating the number of test cases. 

For each testcase, there will be only one line containing two integers  and , indicating the number of problems and the number of people.

For each testcase, output a single integer indicating the minimum hours Walk_alone should wait before the contest is well prepared.

3
0 2
2 2
4 3

0
2
3