Maximum Crates Placement in a Warehouse

In this problem, you are given the dimensions of a warehouse in the form of an L×W grid. Your task is to determine the maximum number of crates that can be placed on this grid under the condition that no two crates are adjacent, nor do they share the same row, column, or diagonal. This is equivalent to finding the maximum independent set on a grid that alternates like a chessboard.

The mathematical solution is to compute the ceiling of \(\frac{L \times W}{2}\), which can be implemented as \(\frac{L\times W + 1}{2}\) using integer arithmetic.

inputFormat

The first line contains an integer T, the number of test cases. Each of the following T lines contains two space-separated integers L and W representing the dimensions of a warehouse.

outputFormat

For each test case, output a single integer representing the maximum number of crates that can be placed, with the answer for each test case printed on a new line.## sample

3
3 3
5 5
6 7

5
13
21