← 返回题目列表

Codeforces · 1715/A

A. 跨市场

中文机器翻译题面 查看原题

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$$$,这是我们的最终答案。