Maximum Domino Placement

You are given an N x M grid. Your task is to determine the maximum number of dominoes that can be placed on the grid without overlapping. Each domino covers exactly two cells.

The answer for each case is given by the formula: $$\left\lfloor \frac{N \times M}{2} \right\rfloor$$

Print the result for each test case on a new line.

inputFormat

The first line contains an integer T indicating the number of test cases. Each of the following T lines contains two space-separated integers N and M representing the dimensions of the grid.

outputFormat

For each test case, output a single line containing the maximum number of dominoes that can be placed on the grid.

## sample

2
2 3
3 3

3
4

</p>