Coloring Rectangles
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 1000
Tags: greedy, math

David was given a red checkered rectangle of size $$$n \times m$$$. But he doesn't like it. So David cuts the original or any other rectangle piece obtained during the cutting into two new pieces along the grid lines. He can do this operation as many times as he wants.

As a result, he will get a set of rectangles. Rectangles $$$1 \times 1$$$ are forbidden.

David also knows how to paint the cells blue. He wants each rectangle from the resulting set of pieces to be colored such that any pair of adjacent cells by side (from the same piece) have different colors.

What is the minimum number of cells David will have to paint?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. The next lines contain descriptions of test cases.

The only line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^4$$$, $$$n \cdot m \geq 2$$$).

Output format:
For each test case print a single integer — the minimum number of cells David will have to paint blue.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The following pictures show how the initial rectangle can be split and cells colored blue.

In the first test case:

In the second test case:

In the third test case:

In the fourth test case:

Example input:
4
1 3
2 2
2 5
3 5

Example output:
1
2
4
5

Editorial:
Rectangles after cutting will be painted in a chess coloring. So, if the area is even, then the number of cells of different colors is the same, and if it is odd, then it differs by exactly $$$1$$$.
Let's find out what part the colored cells occupy in relation to all of them. For an even area, this ratio is always $$$\frac{1}{2}$$$. For odd $$$\frac{S - 1}{2 \cdot S}$$$. The smaller the odd area, the smaller the ratio. An area equal to $$$1$$$ cannot be obtained, so the best ratio is $$$\frac{1}{3}$$$ and is achieved with an area equal to $$$3$$$.
Then we get the lower estimate for the answer: $$$answer \geq n \cdot m \cdot \frac{1}{3}$$$. Great!
We know that the answer is integer, so if we manage to construct such a cut that it is necessary to color exactly such a $$$cnt$$$ of cells that$$$\frac{n \cdot m}{3} \leq cnt < \frac{n \cdot m}{3} + 1$$$, then $$$cnt$$$ will be the answer. After all, $$$cnt$$$ is the minimum integer value satisfying the estimate.
If one of the sides is divisible by $$$3$$$, then it is obvious how to cut into $$$1 \times 3$$$ rectangles and get the perfect answer.
If the remains of sides $$$1$$$ and $$$1$$$ or $$$2$$$ and $$$2$$$, then you can cut into $$$1 \times 3$$$ rectangles and one rectangle with an area of $$$4$$$, in which you need to paint over $$$2$$$ cells. Then the answer also fits the assessment.
If the remains of sides $$$1$$$ and $$$2$$$, then after cutting into $$$1 \times 3$$$ rectangles, a rectangle will remain $$$1 \times 2$$$, in which you need to paint one cell. The answer also fits the assessment.
For all pairs of remains, there is a way to construct an answer satisfying the inequality. Therefore, the answer is $$$ \lceil \frac{n \cdot m}{3} \rceil$$$