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
3 2 2 5 7 3 2
输出 #1
2 7 3
注意
在第一个测试用例中,政府重建城市 $$$(1, 2)$$$ 和 $$$(2, 1)$$$ 就足够了。
在第二个测试用例中,政府重建城市就足够了 $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(3, 6)$$$, $$$(4, 3)$$$, $$$(5, 5)$$$, $$$(5, 7)$$$。