Maze Shortest Path

You are given one or more mazes. Each maze is represented as a grid of m rows and n columns consisting of characters.

The character '.' (dot) represents an open cell, and any other character is considered an obstacle (walls are represented implicitly by obstacles in the maze input). You are also provided with a starting cell and an ending cell (both specified using 1-indexed coordinates). Your task is to determine the length of the shortest path from the start to the end using only moves in the four cardinal directions (up, down, left, right). If there is no valid path, output No Path.

The distance between two adjacent cells is 1. In mathematical terms, if we denote the number of steps as d, you need to find the minimal d such that

\( d = \min \{ \text{number of moves from start to end} \} \)

using a Breadth-First Search (BFS) strategy.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer T representing the number of mazes (test cases).
• For each maze, the first line contains two integers m and n (the number of rows and columns).
• The next line contains two integers representing the starting cell's row and column (1-indexed).
• The following line contains two integers representing the ending cell's row and column (1-indexed).
• Then follow m lines, each containing a string of length n describing the maze. A '.' (dot) indicates an open cell.

outputFormat

For each maze, output a single line containing the length of the shortest path from the start to the end. If there is no such path, output No Path.

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

## sample

1
5 5
1 1
5 5
.....
.###.
..#..
.####
.....

8

</p>