给您一个包含 $$$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$$$。