Minimum Steps in Maze

You are given a maze in the form of a grid with m rows and n columns. Each cell in the grid is either open (O) or blocked (X). Your task is to compute the minimum number of steps required to move from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (m-1, n-1)) by moving only in the four cardinal directions: up, down, left, and right.

If there is no valid path from the start to the destination, output -1.

The problem can be represented mathematically as follows: Given a grid \( G \) where \( G_{ij} \in \{O, X\} \), find the minimum number of moves required such that:

[ \begin{aligned} & (0,0) \to (m-1,n-1), \ & \text{and each move is one of } (0,1), (1,0), (0,-1), (-1,0), \ & \text{with } G_{ij} = O \text{ along the chosen path.} \end{aligned} ]

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, representing the number of rows and columns.
• The following m lines each contain a string of length n consisting of characters O (open) and X (blocked).

Input is provided via standard input (stdin).

outputFormat

For each test case, output the minimum number of steps required to reach the bottom-right corner from the top-left corner. If it is not possible, output -1. Each result should be printed on a separate line via standard output (stdout).

## sample

3
3 3
OOO
OXX
OOO
5 5
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO
2 2
OX
XO

4
8
-1

</p>