Warehouse Pathfinding

In a large warehouse, paths are defined on a rectangular grid. Each cell in the grid is either an empty space represented by . or an obstacle represented by I. Starting from a given cell, you need to find the minimum number of steps required to reach a target cell. You can move in four directions: up, down, left, or right. If the target cell cannot be reached due to obstacles, output -1.

Note: The grid indices are 0-indexed. The number of steps corresponds to the minimum number of moves from the start cell to the target cell using only valid moves in empty cells.

Formal Definition: Given integers \(N\) and \(M\) representing the dimensions of the grid, along with the grid description \(G\) where each \(G_{ij}\) is either . or I, and four integers \(sx, sy, tx, ty\) representing the starting and target positions, find the minimum number of moves required to transport from \((sx,sy)\) to \((tx,ty)\), or output \(-1\) if there is no path.

inputFormat

The input starts with an integer T denoting the number of test cases. Each test case is described as follows:

1. The first line contains two space-separated integers N and M representing the number of rows and columns of the grid.
2. The next N lines each contain a string of length M where each character is either . (an empty cell) or I (an obstacle).
3. The last line of the test case contains four space-separated integers sx, sy, tx, ty representing the row and column of the starting and target cells respectively.

All input is provided through standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum number of steps to reach the target cell from the starting cell. If the target cell cannot be reached, output -1. The output is written to standard output (stdout).

## sample

1
5 5
.....
.I.I.
.I.I.
.I.I.
.....
0 0 4 4

8

</p>