[Solution] Direction Change solution codeforces

Direction Change solution codeforces – You are given a grid with 𝑛n rows and 𝑚m columns. Rows and columns are numbered from 11 to 𝑛n, and from 11 to 𝑚m. The intersection of the 𝑎a-th row and 𝑏b-th column is denoted by (𝑎,𝑏)(a,b).

[Solution] Direction Change solution codeforces

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

You can move in four directions from (𝑎,𝑏)(a,b): up to (𝑎1,𝑏)(a−1,b), down to (𝑎+1,𝑏)(a+1,b), left to (𝑎,𝑏1)(a,b−1) or right to (𝑎,𝑏+1)(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𝑡1031≤t≤103) — 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𝑛,𝑚1091≤n,m≤109) — the size of the grid.

[Solution] Direction Change solution codeforces

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

Example
input

Copy
6
1 1
2 1
1 3
4 2
4 6
10 5
output

Copy
0
1
-1
6
10
17

Direction Change solution codeforces

Test case 11𝑛=1n=1𝑚=1m=1, and initially you are standing in (1,1)(1,1) so 00 move is required to reach (𝑛,𝑚)=(1,1)(n,m)=(1,1).

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

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

Test case 44: an optimal moving sequence could be: (1,1)(1,2)(2,2)(2,1)(3,1)(3,2)(4,2)(1,1)→(1,2)→(2,2)→(2,1)→(3,1)→(3,2)→(4,2). It can be proved that this is the optimal solution. So the answer is 66.

 

For Solution

Click here

Leave a Comment