Minimum Steps to Exit the Grid

You are given a grid with n rows and m columns. Each cell in the grid is either 'O' (open) or 'X' (blocked). You start at the cell in the top-left corner (cell (0, 0)) and need to reach the bottom-right corner (cell (n-1, m-1)). You can only move one cell at a time in one of the four cardinal directions (up, down, left, or right).

If either the starting cell or the destination cell is blocked, or if there is no valid path between them, return \( -1 \). Otherwise, output the minimum number of steps required to reach the destination.

The problem can be formalized as follows: Given a grid \( G \) of size \( n \times m \), find the minimum number of steps required to move from \( G_{0,0} \) to \( G_{n-1,m-1} \) using only allowed moves. If it is impossible to reach the destination, output \( -1 \>.

inputFormat

The first line of the input contains an integer \( T \) representing the number of test cases. Each test case is described as follows:

• The first line contains two integers \( n \) and \( m \) representing the number of rows and columns in the grid.
• This is followed by \( n \) lines, each containing a string of length \( m \) consisting of the characters 'O' and 'X'.

The input should be read from standard input (stdin).

outputFormat

For each test case, output one line containing a single integer: the minimum number of steps required to reach the bottom-right corner from the top-left corner, or \( -1 \) if no valid path exists.

The output should be written to standard output (stdout).

## sample

2
3 3
OXO
OXO
OOO
4 4
OXOX
XOOX
OOXX
OXOX

4
-1

</p>