Minimum Moves in Booster Grid

You are given a grid of size \(N \times M\) where each cell contains either 0 or 1. You start at the top-left corner (cell (1,1)) and your goal is to reach the bottom-right corner (cell (N,M)). Under normal conditions, you can only move right or down. However, if you step onto a cell containing a 1 (a booster cell), you are allowed to take an extra step immediately in any of the four directions (up, down, left, or right). The extra step incurred when stepping on a booster cell costs an additional move.

Your task is to determine the minimum number of moves required to reach the destination. If it is not possible to reach the bottom-right corner, output \(-1\).

Note: Moves that take you outside the grid are not allowed.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each test case begins with a line containing two integers \(N\) and \(M\) representing the number of rows and columns, respectively. This is followed by \(N\) lines, each containing \(M\) space-separated integers (either 0 or 1) that represent the grid.

outputFormat

For each test case, output a single integer on a new line indicating the minimum number of moves required to reach the bottom-right corner of the grid. If no valid path exists, output \(-1\).

## sample

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

5
2
0

</p>