Maximal Tree Planting

You are given a rectangular garden with dimensions M x N. Your task is to determine the maximum number of trees that can be planted in the garden such that no two trees are adjacent vertically, horizontally, or diagonally.

This means that if a tree is planted at position \( (i, j) \), then positions \( (i-1, j-1) \), \( (i-1, j) \), \( (i-1, j+1) \), \( (i, j-1) \), \( (i, j+1) \), \( (i+1, j-1) \), \( (i+1, j) \), and \( (i+1, j+1) \) must remain empty.

The optimal solution is to use a checkerboard pattern. The maximum number of trees that can be planted is given by the formula:

[ \text{max_trees} = \left\lceil \frac{M \times N}{2} \right\rceil = \frac{M \times N + 1}{2} ]

Implement a program that reads multiple test cases from standard input and outputs the result for each test case.

inputFormat

The first line of input contains a single integer T representing the number of test cases.

Each of the next T lines contains two integers M and N separated by a space, representing the dimensions of the garden.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number of trees that can be planted in the garden.

Output is written to standard output (stdout).

## sample

2
2 2
3 3

2
5

</p>