Maximizing Flower Planting in a Garden

In this problem, you are given a rectangular garden with dimensions (N) rows and (M) columns. Your task is to plant as many flowers as possible such that no two flowers are adjacent horizontally or vertically. Note that the optimal solution is to plant the flowers in a chessboard pattern. Mathematically, the maximum number of flowers that can be planted is given by [ \left\lceil \frac{N \times M}{2} \right\rceil ] where (\lceil \cdot \rceil) denotes the ceiling function. Make sure your program reads input from standard input and writes the output to standard output.

inputFormat

The input begins with a single integer (T) ((1 \le T \le 10^4)), the number of test cases. Each of the following (T) lines contains two space-separated integers (N) and (M) ((1 \le N, M \le 10^9)) representing the dimensions of the garden.

outputFormat

For each test case, output a single line containing the maximum number of flowers that can be planted in the garden such that no two flowers are adjacent horizontally or vertically.## sample

1
3 3

5