CF1905A.Constructive Problems

Gridlandia has been hit by flooding and now has to reconstruct all of it's cities. Gridlandia can be described by an $n \times m$ matrix.

Initially, all of its cities are in economic collapse. The government can choose to rebuild certain cities. Additionally, any collapsed city which has at least one vertically neighboring rebuilt city and at least one horizontally neighboring rebuilt city can ask for aid from them and become rebuilt without help from the government. More formally, collapsed city positioned in $(i, j)$ can become rebuilt if both of the following conditions are satisfied:

• At least one of cities with positions $(i + 1, j)$ and $(i - 1, j)$ is rebuilt;
• At least one of cities with positions $(i, j + 1)$ and $(i, j - 1)$ is rebuilt.

If the city is located on the border of the matrix and has only one horizontally or vertically neighbouring city, then we consider only that city.

Illustration of two possible ways cities can be rebuilt by adjacent aid. White cells are collapsed cities, yellow cells are initially rebuilt cities (either by the government or adjacent aid), and orange cells are rebuilt cities after adjacent aid.

The government wants to know the minimum number of cities it has to rebuild such that after some time all the cities can be rebuild.

Gridlandia 遭遇了洪水侵袭，如今需要重建所有城市。Gridlandia 可用一个 $n \times m$ 的矩阵来描述。

初始时，所有城市均处于经济崩溃状态。政府可选择重建其中若干城市。此外，若某个崩溃城市至少有一个垂直方向相邻的已重建城市，且至少有一个水平方向相邻的已重建城市，则该崩溃城市可向它们申请援助，并在无需政府直接帮助的情况下自行重建。更准确地说，位于 $(i, j)$ 的崩溃城市可在满足以下两个条件时被重建：

• 城市 $(i + 1, j)$ 和 $(i - 1, j)$ 中至少有一个已被重建；
• 城市 $(i, j + 1)$ 和 $(i, j - 1)$ 中至少有一个已被重建。

若某城市位于矩阵边界上，其水平或垂直方向的相邻城市少于两个，则仅考虑实际存在的那些相邻城市。

图示：城市通过相邻援助实现重建的两种可能方式。白色格子表示崩溃城市，黄色格子表示初始即被重建的城市（由政府直接重建或通过相邻援助重建），橙色格子表示后续通过相邻援助重建的城市。

政府希望知道：为使最终所有城市均能被重建，它所需最少直接重建的城市数量是多少？

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 100$) — the sizes of Gridlandia.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$2 \le n, m \le 100$），表示 Gridlandia 的尺寸。

For each test case, output a single integer — the minimum number of cities the government needs to rebuild.

对于每个测试用例，输出一个整数——政府需要重建的最少城市数量。

In the first test case, it's enough for the government to rebuild cities $(1, 2)$ and $(2, 1)$.

In the second test case, it's enough for the government to rebuild cities $(1, 4)$, $(2, 2)$, $(3, 1)$, $(3, 6)$, $(4, 3)$, $(5, 5)$, $(5, 7)$.

在第一个测试用例中，政府只需重建城市 $(1, 2)$ 和 $(2, 1)$ 即可。

在第二个测试用例中，政府只需重建城市 $(1, 4)$、$(2, 2)$、$(3, 1)$、$(3, 6)$、$(4, 3)$、$(5, 5)$、$(5, 7)$ 即可。