Evil Sahu and his Virus
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
Y), 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).
First line contain an integer T, the number of test cases.
Next T line contains two integer X and Y.
Output minimum time in minutes, it will take for virus to infect the entire lab.
T <= 1000
0 <= X <= 1000000
0 <= Y <= 1000000
Problem Setter : Pushkar Anand
Problem Tester: Shikhar Sharad