Direction Change

1000ms

262144K

Description:

You are given a grid with $$$n$$$ rows and $$$m$$$ columns. Rows and columns are numbered from $$$1$$$ to $$$n$$$, and from $$$1$$$ to $$$m$$$. The intersection of the $$$a$$$-th row and $$$b$$$-th column is denoted by $$$(a, b)$$$.

Initially, you are standing in the top left corner $$$(1, 1)$$$. Your goal is to reach the bottom right corner $$$(n, m)$$$.

You can move in four directions from $$$(a, b)$$$: up to $$$(a-1, b)$$$, down to $$$(a+1, b)$$$, left to $$$(a, b-1)$$$ or right to $$$(a, b+1)$$$.

You cannot move in the same direction in two consecutive moves, and you cannot leave the grid. What is the minimum number of moves to reach $$$(n, m)$$$?

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of the test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the size of the grid.

Output:

For each test case, print a single integer: $$$-1$$$ if it is impossible to reach $$$(n, m)$$$ under the given conditions, otherwise the minimum number of moves.

Sample Input:

Sample Output:

Note:

Test case $$$1$$$: $$$n=1$$$, $$$m=1$$$, and initially you are standing in $$$(1, 1)$$$ so $$$0$$$ move is required to reach $$$(n, m) = (1, 1)$$$.

Test case $$$2$$$: you should go down to reach $$$(2, 1)$$$.

Test case $$$3$$$: it is impossible to reach $$$(1, 3)$$$ without moving right two consecutive times, or without leaving the grid.

Test case $$$4$$$: an optimal moving sequence could be: $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)$$$. It can be proved that this is the optimal solution. So the answer is $$$6$$$.

Informação

Provedor Codeforces

Código CF1668A