EIU Programming Practices and Exams

XYZ University is located in a rectangular campus divided into n rows and m columns. The school want to upgrade wifi system with special access points (APs). If the AP is located in cell (x, y), the adjacent cells (including the diagonal) will receive the wifi signal. Because the probability of students who sit in the adjacent cells of the fence (boundary of the campus) is very small, these cells do not require wifi. The school's IT department wants you to determine at least how many transmitters are needed to cover the compus

Input

The first line is the number of testcases T(T<1000)

In the next T lines, each line describes a test case consisting of 2 numbers n, m (n, m <10 ^ 18) as the campus size.

Output

For each test case, output the minimum number of wifi AP needed to use . The result is always less than 10 ^ 18.

Input:
2
3 3
7 7

Output:
1
4