题目描述

题目背景

在宏伟却冷清的辉针城深处，一个连阳光都难以直射的、堆满杂物的偏僻角落，少名针妙丸找到了属于她的秘密乐园。这里没有宝槌的沉重，没有一族的期许，只有她自己。

她今天收集的材料格外丰富：清晨从巨大花瓣上摇落的、圆润如珍珠的露水；被风吹进来的、颜色各异的细小花瓣和嫩叶；还有一些不知从哪里来的、闪闪发光的矿物碎屑和彩色玻璃渣。这些都是她眼中的无价之宝。

她哼着即兴编造的、不成调但欢快的小曲，开始工作。先用小石子围出一个规则的圆形，将“露珠珍珠”小心地倒进去——她的“镜湖”诞生了。然后，她用湿润的苔藓铺出连绵的“小山”，插上细小的枝条作为“树林”。最精巧的是，她找到了一片极小的、心形的绿色叶子，把它轻轻放在“镜湖”中央，用一截肉眼几乎看不见的蛛丝固定——这是她的“青苔扁舟”。

她趴在地上，湛蓝的大眼睛一眨不眨地凝视着自己的作品，小小的胸膛里充满了巨大的成就感。她想象着有微小的仙子住在苔藓森林里，想象着那叶小舟会载着它们去湖心探险。这一刻，她不是付丧神，不是被迫背负复兴重任的弱小神明，只是一个完全沉醉在自己编织的童话王国里的、快乐又普通的小小人女孩。辉针城的冰冷与巨大，仿佛都成了保护这个微缩庭园的、遥远的背景墙。阳光艰难地转过一个角度，终于有一缕金线般的光芒穿过缝隙，恰好照亮了她的“镜湖”和小舟，一切都在瞬间变得璀璨夺目。针妙丸屏住呼吸，生怕惊扰了这魔法般的时刻，脸上露出了无比幸福的笑容。

题目描述

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

现在少名针妙丸脚下有一块由 \(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\)）。

输出格式

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

样例输入

5
1 1
2 2
3 3
4 4
5 5

样例输出

1
0
5
4
13