A. 构造性问题

每个测试点的时间限制： $1$ 秒

每个测试点的内存限制： $256$ 兆字节

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$ ，表示 Gridlandia 的大小，其中 $2 \le n, m \le 100$ 。

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

样例输入

样例输出

2
7
3

在第 $1$ 组测试数据中，政府只需要重建城市 $(1,2)$ 和 $(2,1)$ 即可。

在第 $2$ 组测试数据中，一种可行方案是政府重建以下城市：

$(1,4)$ 、 $(2,2)$ 、 $(3,1)$ 、 $(3,6)$ 、 $(4,3)$ 、 $(5,5)$ 、 $(5,7)$ 。