Robot Race Challenge

You are given a grid of size \(M \times N\). Each cell in the grid is either free (denoted by '0') or an obstacle (denoted by '1'). A robot starts at the top-left corner of the grid (cell (0, 0)) and needs to reach the bottom-right corner (cell (M-1, N-1)). The robot can move one step in any of the four directions: up, down, left, or right. Your task is to determine the minimum number of steps required for the robot to reach the destination. If there is no valid path from the start to the destination, output -1.

Note: The moves allowed are up, down, left, and right, and the robot cannot move diagonally. The grid is provided as an array of strings where each character represents a cell's state.

inputFormat

The input is given from standard input (stdin) and is structured as follows:

• The first line contains a single integer \(T\) representing the number of test cases.
• For each test case, the first line contains two integers \(M\) and \(N\), representing the number of rows and columns in the grid.
• This is followed by \(M\) lines, each containing a string of length \(N\) composed of the characters '0' (free cell) and '1' (obstacle).

Each test case should be processed independently.

outputFormat

For each test case, output a single integer on a new line, representing the minimum number of steps the robot needs to reach from the top-left corner to the bottom-right corner. If it is not possible to reach the destination, output -1.

## sample

5
3 3
000
010
000
4 4
0000
1110
0000
0110
2 2
00
00
2 2
01
10
1 4
0000

4
6
2
-1
3

</p>