题目描述

David 得到了一块大小为 $n \times m$ 的红色格子矩形。但他并不喜欢它。因此，David 可以将原始矩形或在切割过程中得到的任意矩形沿着网格线切割成两块新的矩形。他可以进行任意多次这样的操作。

最终，他会得到一组矩形。禁止出现 $1 \times 1$ 的矩形。

David 还会把格子涂成蓝色。他希望对每个最终得到的矩形进行染色，使得同一块矩形中任意一对相邻（共边）的格子颜色不同。

请问，David 至少需要涂多少个格子为蓝色？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。接下来的每组测试用例描述如下。

每组测试用例包含一行，包含两个整数 $n$、$m$（$1 \leq n, m \leq 3 \times 10^4$，$n \cdot m \geq 2$）。

输出格式

对于每个测试用例，输出一个整数，表示 David 至少需要涂成蓝色的格子数。

说明/提示

下图展示了初始矩形如何被切割以及格子如何染成蓝色。

对于第一个测试用例：

对于第二个测试用例：

对于第三个测试用例：

对于第四个测试用例：

由 ChatGPT 4.1 翻译

样例

4
1 3
2 2
2 5
3 5

1
2
4
5