← 返回题目列表

Codeforces · 1668/A

A. 方向改变

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

给您一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。行和列的编号从 $$$1$$$ 到 $$$n$$$,从 $$$1$$$ 到 $$$m$$$。第 $$$a$$$ 行和第 $$$b$$$ 列的交集由 $$$(a, b)$$$ 表示。

最初,您站在左上角$$$(1, 1)$$$。您的目标是到达右下角$$$(n, m)$$$。

您可以从 $$$(a, b)$$$ 向四个方向移动:向上到 $$$(a-1, b)$$$、向下到 $$$(a+1, b)$$$、向左到 $$$(a, b-1)$$$ 或向右到 $$$(a, b+1)$$$。

你不能连续两次向同一方向移动,也不能离开网格。达到 $$$(n, m)$$$ 的最少移动次数是多少?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — 网格的大小。

输出

对于每个测试用例,如果在给定条件下不可能达到 $$$(n, m)$$$,则打印单个整数:$$$-1$$$,否则打印最小移动数。

示例

输入 #1

6
1 1
2 1
1 3
4 2
4 6
10 5

输出 #1

0
1
-1
6
10
17

注意

测试用例$$$1$$$:$$$n=1$$$,$$$m=1$$$,最初你站在$$$(1, 1)$$$,所以需要$$$0$$$移动才能到达$$$(n, m) = (1, 1)$$$。

测试用例 $$$2$$$:您应该向下到达 $$$(2, 1)$$$。

测试用例$$$3$$$:如果不连续两次向右移动,或者不离开网格,就不可能到达$$$(1, 3)$$$。

测试用例 $$$4$$$:最佳移动顺序可以是: $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)$$$。可以证明这是最优解。所以答案是$$$6$$$。