题目描述

少名针妙丸在玩一款叫做「你的克拉夫特」的游戏。在这个游戏里，少名针妙丸可以在一个充满着方块的三维空间中自由地创造和破坏不同种类的方块。

现在少名针妙丸脚下有一块由 $N\times M$ 个格子组成的网格。一开始，少名针妙丸在这些格子上铺满了白色地毯，然后少名针妙丸就去睡觉了。

但是不幸的是，在少名针妙丸睡觉的时候，你希望对少名针妙丸的地毯进行一些小小的修改。你希望将其中一些白色地毯改成黑色地毯，同时满足下面两个条件：

条件 $1$ ：任意两个黑色地毯所在的格子不能共享公共边，即满足：
若第 $i$ 行第 $j$ 列格子中为黑色地毯，则第 $i−1$ 行第 $j$ 列、第 $i+1$ 行第 $j$ 列、第 $i$ 行第 $j−1$ 列、第 $i$ 行第 $j+1$ 列格子中如果存在地毯，则不能为黑色地毯。
条件 $2$ ：最终形成的图案至少存在一条水平或者竖直的对称轴，即下面两个命题中至少满足一个：
对于任意的 $i \in [1,N]$ 和 $j \in [1,M]$ ，第 $i$ 行第 $j$ 列格子中的地毯颜色与第 $N−i+1$ 行第 $j$ 列格子中的地毯颜色相同；
对于任意的 $i \in [1,N]$ 和 $j \in [1,M]$ ，第 $i$ 行第 $j$ 列格子中的地毯颜色与第 $i$ 行第 $M−j+1$ 列格子中的地毯颜色相同。

你想要求出：最多可以放置多少块黑色地毯？

输入描述

输入的第一行包含一个整数 $t$ （ $1 \le t \le 2 \times 10^4$ ），表示测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例，输入一行，包含两个整数 $N$ 和 $M$ （ $1 \le N,M \le 10^9$ ）。

对于每个测试用例，输出一行一个整数，表示最多可以放置的黑色地毯数量。