David 得到了一个大小为 $$$n \times m$$$ 的红色方格矩形。但他不喜欢这样。因此,大卫将原始的或在切割过程中获得的任何其他矩形块沿着网格线切割成两个新的块。他可以根据需要多次执行此操作。
结果,他将得到一组矩形。禁止使用矩形 $$$1 \times 1$$$。
David 还知道如何将单元格涂成蓝色。他希望所得到的一组块中的每个矩形都被着色,以便任何相邻的单元对(来自同一块)具有不同的颜色。
David 必须绘制的最小单元格数量是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例的唯一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^4$$$, $$$n \cdot m \geq 2$$$)。
输出
对于每个测试用例,打印一个整数 - David 必须涂成蓝色的最小单元格数。
示例
输入 #1
4 1 3 2 2 2 5 3 5
输出 #1
1 2 4 5
注意
下图显示了如何分割初始矩形并将单元格涂成蓝色。
在第一个测试用例中:
在第二个测试用例中:
在第三个测试用例中:
在第四个测试用例中: