题目描述

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 的规模。

输出格式

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

说明/提示

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

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

由 ChatGPT 4.1 翻译

样例

3
2 2
5 7
3 2

2
7
3