Stanley 和 Megan 决定在“Crossmarket”杂货店购物,该杂货店可以表示为具有 $$$n$$$ 行和 $$$m$$$ 列的矩阵。
斯坦利和梅根可以使用 $$$1$$$ 能量单位移动到相邻的牢房。如果两个单元共享一条边,则它们被视为相邻。为了加快购物过程,梅根随身携带了她的门户,并在她访问的每个牢房中留下一个(如果还没有门户)。如果一个人(斯坦利或梅根)位于有传送门的牢房中,则该人可以使用 $$$1$$$ 能量单位传送到任何其他有传送门的牢房,包括梅根的起始牢房。
他们决定分开:Stanley将从左上角的单元格(坐标为$$$(1, 1)$$$的单元格)到右下角的单元格(坐标为$$$(n, m)$$$的单元格),而Megan需要从左下角的单元格(坐标为$$$(n, 1)$$$的单元格)到右上的单元格(坐标为$$$(1,米)$$$)。
他们俩做到这一点所需的最小总能量是多少?
请注意,他们可以选择移动的时间。时间不影响能量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
测试用例中唯一的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$)。
输出
对于每个测试用例,在新行上打印一个整数 - 答案。
示例
输入 #1
7 7 5 5 7 1 1 100000 100000 57 228 1 5 5 1
输出 #1
15 15 0 299998 340 5 5
注意
在第一个测试用例中,他们可以坚持以下计划:
1. Megan(红色圆圈)移动到单元格 $$$(7, 3)$$$。然后她转到单元格 $$$(1, 3)$$$,斯坦利(蓝色圆圈)也执行同样的操作。
2. Stanley 使用该单元格中的传送门(具有传送门的单元格为灰色)到达单元格 $$$(7, 3)$$$。然后他移动到目的地——单元格$$$(7, 5)$$$。
3. Megan 也完成了她的路线并前往单元格 $$$(1, 5)$$$。
消耗的总能量为$$$(2 + 6) + (2 + 1 + 2) + (2)= 15$$$,这是我们的最终答案。