All Submissions


Just after joining BIT evil Sahu started forging plans for world domination. But as we all know, schedule in BIT is very hectic and what little time one can get after classes is mostly wasted on writing lab journals, preparing for quizzes, etc. And so evil Sahu wrote a computer virus to take down all the computers in lab.
Since computers in lab are arranged in grid (of size XxY), evil Sahu designed this virus to be self-propagating, which means he has to release it to only 1 computer to affect the entire grid. After it affects a computer, it spreads to nearby computers (4 computers) adjacent to it and start hacking them. It takes about a minute for it to propagate from one computer to another also it takes him about a minute to plant the virus. Now evil Sahu want to know the least time it will take to take down the entire lab! And since he is all tired up, he want you to write a program to this (as he knows that you too hate labs :P).

Input
First line contain an integer T, the number of test cases.
Next T line contains two integer X and Y.

Output
Output minimum time in minutes, it will take for virus to infect the entire lab.

Constrain
T <= 1000
0 <= X <= 1000000
0 <= Y <= 1000000

Sample Input

2
3 1
3 3


Sample Output

2
3


Problem Setter : Pushkar Anand
Problem Tester: Shikhar Sharad

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0