Warehouse Robot Navigation

You are given a grid of size \(M \times N\), where each cell is either empty (denoted by .) or blocked (denoted by #). A warehouse robot starts at a given cell and has to reach a target cell by moving one cell at a time in one of the four cardinal directions (up, down, left, right). The task is to find the minimum number of steps required to reach the target cell. If the target is unreachable, output \(-1\).

Note: The grid coordinates are 0-indexed. The input consists of multiple test cases.

The problem can be formally stated as follows:

Given a grid \(G\) of size \(M \times N\), a starting cell \((x_s, y_s)\) and a target cell \((x_t, y_t)\), determine the minimum number of moves required to go from \((x_s, y_s)\) to \((x_t, y_t)\) using only movements in the four cardinal directions and only moving to cells that are not blocked. If there is no valid path, output \(-1\).

inputFormat

The input is given via stdin and has the following format:

T
M N
row1
row2
... (M rows in total)
x_s y_s
x_t y_t
... (repeated for each test case)

Here, \(T\) is 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 of the grid. The next \(M\) lines each contains a string of length \(N\) representing the grid, where . denotes an empty cell and # denotes an obstacle. This is followed by a line with two integers \(x_s\) and \(y_s\) (the starting cell coordinates) and another line with two integers \(x_t\) and \(y_t\) (the target cell coordinates).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of steps required for the robot to reach the target cell. If it is impossible to reach the target, output -1.

## sample

2
5 5
.....
.#.#.
.#.#.
.#.#.
.....
0 0
4 4
5 5
..###
.#...
.#.#.
.#..#
#.###
0 0
4 4

8
-1

</p>