Shortest Path in an Island Grid

You are given a grid representing an island of size \(m \times n\). Each cell of the grid contains an integer that can be 0, 1, or 2. You start at the top-left cell \((0,0)\) and your goal is to reach the bottom-right cell \((m-1, n-1)\).

You can move up, down, left, or right. Under normal conditions, you can move into a cell if its value is either 1 or 2. However, if you are currently on a cell with value 2, you are allowed to move into an adjacent cell even if its value is 0.

If the starting cell \(grid[0][0]\) is 0, then the path is blocked and the answer is \(-1\). Similarly, if there is no valid path from the starting cell to the target cell, output \(-1\). Otherwise, output the minimum number of moves required to reach the destination.

Note: Each move increments the step count by 1.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains two integers \(m\) and \(n\) separated by a space, indicating the number of rows and columns respectively. This is followed by \(m\) lines, each containing \(n\) space-separated integers representing the grid.

Example:

3
3 3
1 0 0
2 2 0
1 1 1
3 3
0 0 0
2 2 0
1 1 1
4 4
1 0 2 2
1 1 0 1
0 2 1 2
0 1 0 2

outputFormat

For each test case, output a single integer representing the minimum number of moves required to go from the top-left to the bottom-right cell. If the destination is unreachable, output \(-1\).

The answers for different test cases should be printed on separate lines.

## sample

3
3 3
1 0 0
2 2 0
1 1 1
3 3
0 0 0
2 2 0
1 1 1
4 4
1 0 2 2
1 1 0 1
0 2 1 2
0 1 0 2

4
-1
6

</p>