Minimum Moves in a Grid

You are given a grid of size \( n \times m \) where each cell is either a free cell denoted by . or an obstacle denoted by #. For each test case, you are provided with a starting position \((sr, sc)\) and a destination position \((dr, dc)\). Your task is to determine the minimum number of moves required to travel from the start to the destination moving only in the four cardinal directions (up, down, left, right). If the destination cannot be reached, output \(-1\).

Note: The positions provided are 1-indexed. A move consists of moving one cell vertically or horizontally into a free cell.

inputFormat

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

n m t
sr sc dr dc
row1
row2
... (n rows representing the grid)
(repeat the above test-case block t times)

Where:

• \( n \) and \( m \) are the number of rows and columns of the grid.
• \( t \) is the number of test cases.
• For each test case, \( sr \), \( sc \), \( dr \), and \( dc \) represent the starting row, starting column, destination row, and destination column respectively.
• Each grid consists of n lines, each with m characters (either . or #).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of moves required to reach the destination, or \(-1\) if it is impossible.

## sample

4 4 2
1 1 4 4
.#..
.##.
..#.
...#
1 1 2 2
..##
..##
.##.
....

-1
2

</p>