Shortest Path in a Park

You are given a rectangular grid park of size \(N \times M\). Each cell in the grid is either empty (represented by a '.') or has a tree (represented by a '#'). There is a unique entrance and a unique exit in the park. You can move one step at a time from a cell to one of its neighbors (up, down, left, or right) if the destination cell is empty.

Your task is to determine the minimum number of steps required to travel from the entrance to the exit while avoiding trees. If the exit is unreachable, output -1.

Note: All coordinates are 1-indexed.

The problem can be formally stated using the following details:

Given an input with \(T\) test cases, where each test case includes:

• Two integers \(N\) and \(M\): the dimensions of the park.
• \(N\) lines each containing \(M\) characters (either '.' or '#').
• A line with four integers \(x_1, y_1, x_2, y_2\) representing the entrance and exit coordinates respectively.

You should output for each test case a line in the format "Test Case #X: Y" where X is the test case number (starting from 1) and Y is the minimum number of steps needed to go from the entrance to the exit (or -1 if unreachable).

inputFormat

The first line contains an integer \(T\), the number of test cases.

For each test case:

• The first line contains two integers \(N\) and \(M\), denoting the number of rows and columns.
• The next \(N\) lines each contain a string of length \(M\) representing the park layout ('.' for an empty cell, '#' for a tree).
• The next line contains four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) representing the entrance and the exit coordinates respectively (1-indexed).

All input is provided via standard input (stdin).

outputFormat

For each test case, print a single line in the format "Test Case #X: Y" where X is the test case number (starting from 1) and Y is the minimum number of steps needed to go from the entrance to the exit, or -1 if no such path exists. Output should be printed to standard output (stdout).

## sample

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

Test Case #1: -1
Test Case #2: 6

</p>