CF1584B.Coloring Rectangles

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?

大卫得到了一个大小为 $n \times m$ 的红色方格矩形。但他不喜欢它。因此，大卫沿着网格线将原始矩形或在切割过程中得到的任意其他矩形切分为两个新矩形。他可以执行该操作任意多次。

最终，他将得到一组矩形。其中 $1 \times 1$ 的矩形是禁止出现的。

大卫还掌握了将方格涂成蓝色的方法。他希望对最终所得所有矩形碎片中的每个矩形进行染色，使得同一碎片中任意两个边相邻的方格颜色不同。

大卫最少需要将多少个方格涂成蓝色？

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$).

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。接下来的行包含各测试用例的描述。

每个测试用例仅一行，包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \cdot 10^4$，且 $n \cdot m \geq 2$）。

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

对于每个测试用例，输出一个整数——David 需要涂成蓝色的最少格子数。

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:

以下图片展示了初始矩形如何被分割以及单元格如何被染成蓝色。

第一个测试用例：

第二个测试用例：

第三个测试用例：

第四个测试用例：