310886: CF1905A. Constructive Problems

A. Constructive Problemstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput

3
2 2
5 7
3 2

Output

2
7
3

Note

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

题目大意：
Gridlandia遭受洪水袭击，现需重建所有城市。Gridlandia可以表示为一个 $ n \times m $ 的矩阵。

最初，所有城市都处于经济崩溃状态。政府可以选择重建某些城市。此外，任何处于崩溃状态的城市，如果它至少有一个垂直相邻的已重建城市和至少一个水平相邻的已重建城市，它可以向它们请求援助并自行重建（无需政府帮助）。更正式地说，位于 $ (i, j) $ 的崩溃城市可以重建，如果满足以下两个条件：

- 至少有一个位于 $ (i + 1, j) $ 和 $ (i - 1, j) $ 位置的城市已重建；
- 至少有一个位于 $ (i, j + 1) $ 和 $ (i, j - 1) $ 位置的城市已重建。

如果城市位于矩阵的边缘，并且只有一个水平或垂直相邻的城市，那么我们只考虑那个城市。

政府想知道它至少需要重建多少个城市，以便在一段时间后所有城市都能重建。

输入输出数据格式：

输入：
每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例只有一行，包含两个整数 $ n $ 和 $ m $ ($ 2 \le n, m \le 100 $) —— Gridlandia的大小。

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

示例：

输入：
```
3
2 2
5 7
3 2
```

输出：
```
2
7
3
```

注意：
- 在第一个测试用例中，政府只需重建城市 $ (1, 2) $ 和 $ (2, 1) $。
- 在第二个测试用例中，政府只需重建城市 $ (1, 4) $, $ (2, 2) $, $ (3, 1) $, $ (3, 6) $, $ (4, 3) $, $ (5, 5) $, $ (5, 7) $。题目大意： Gridlandia遭受洪水袭击，现需重建所有城市。Gridlandia可以表示为一个 $ n \times m $ 的矩阵。 最初，所有城市都处于经济崩溃状态。政府可以选择重建某些城市。此外，任何处于崩溃状态的城市，如果它至少有一个垂直相邻的已重建城市和至少一个水平相邻的已重建城市，它可以向它们请求援助并自行重建（无需政府帮助）。更正式地说，位于 $ (i, j) $ 的崩溃城市可以重建，如果满足以下两个条件： - 至少有一个位于 $ (i + 1, j) $ 和 $ (i - 1, j) $ 位置的城市已重建； - 至少有一个位于 $ (i, j + 1) $ 和 $ (i, j - 1) $ 位置的城市已重建。 如果城市位于矩阵的边缘，并且只有一个水平或垂直相邻的城市，那么我们只考虑那个城市。 政府想知道它至少需要重建多少个城市，以便在一段时间后所有城市都能重建。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例只有一行，包含两个整数 $ n $ 和 $ m $ ($ 2 \le n, m \le 100 $) —— Gridlandia的大小。 输出： 对于每个测试用例，输出一个整数 —— 政府需要重建的最少城市数量。 示例： 输入： ``` 3 2 2 5 7 3 2 ``` 输出： ``` 2 7 3 ``` 注意： - 在第一个测试用例中，政府只需重建城市 $ (1, 2) $ 和 $ (2, 1) $。 - 在第二个测试用例中，政府只需重建城市 $ (1, 4) $, $ (2, 2) $, $ (3, 1) $, $ (3, 6) $, $ (4, 3) $, $ (5, 5) $, $ (5, 7) $。