Given a maze in the form of a binary rectangular matrix of size M*N, where each element can either be 0 or 1, the task is to find the length of the shortest path in a maze from a given source cell to a destination cell.

The path can only be created out of a cell if its value is 1 and at any given moment, we can only move one step in one of the four directions. The valid moves are:

Up: (x, y) -> (x - 1, y)
Left: (x, y) -> (x, y - 1)
Down: (x, y) -> (x + 1, y)
Right: (x, y) -> (x, y + 1)

If there is no path from a given source cell to a destination cell, return -1.

For example :

consider the binary matrix below. If source = (0, 0) and destination = (3, 4), the shortest path from source to destination has length 11.

Input Format :

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers M and N, representing the number of rows and columns respectively.

Each of the next M lines contains N space-separated integers representing the matrix.

The last second line of each test case contains two space-separated integers denoting the coordinates of the source cell.

The last line of each test case contains two space-separated integers denoting the coordinates of the destination cell.

For example, the input for the binary matrix depicted in the below image would be:

3 4
1 1 1 1
0 1 1 0
0 0 1 1
0 0
2 3

Explanation :

The first line represents that the given matrix has 3 rows and 4 columns.
Each of the next 3 lines contains 4 space-separated integers representing a row.
Last second line contains two space-separated integers representing coordinates of the source cell, i.e. (0, 0).
The last line contains two space-separated integers representing coordinates of the destination cell, i.e. (2, 3).

Output Format :

For each test case, print a single integer denoting the length of the shortest path between a given source cell to a destination cell. If such a path does not exist, print -1.

The output for each test case is in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= M, N <= 100

Time Limit: 1sec