Maximum Dominoes

You are given a rectangular board with width W and height H. Your task is to determine the maximum number of 2x1 dominoes that can be placed on the board without overlapping. A domino occupies exactly 2 cells. The answer is computed as:

\(\left\lfloor \frac{W \times H}{2} \right\rfloor\)

For example, for a board of dimensions 2x3, the maximum number of dominoes is \(\lfloor 6/2 \rfloor = 3\).

Read the input from standard input (stdin) and print the result on standard output (stdout) for each test case.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 10⁵), the number of test cases.

Each of the following T lines contains two space-separated integers W and H (1 ≤ W, H ≤ 10⁹), representing the width and height of the board respectively.

outputFormat

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

## sample

3
2 3
4 4
2 2

3
8
2

</p>