Anna University Local Contest #10

Statement :

In pipe games, your objective is to arrange pipes such that there is water flowing from a source to destination. In our variation of the game, there is an unlimited supply of water. Consider a grid of size N x M. In each cell of the grid, there is a pipe shape(the details are given below). You are able to rotate the pipe shapes 90 degrees clockwise or anti-clockwise any number of times. You cannot move the pipe shapes from the cell. The source is from the left side of the top left cell and the destination is the right side of the bottom right cell. You have to make a minimum number of rotations such that a path exists from the source to the destination. Since there is an unlimited supply of water don’t worry about open ends. Note that water cannot flow from bottom to top since it defies gravity. Water can flow in all other directions.

The pipe shapes are:

1. Horizontal pipe(connects left and right)

2. Vertical pipe(connects top and bottom)

3. L shape-1(connects top and left)

4. L shape-2(connects top and right)

5. L shape-3(connects bottom and left)

6. L shape-4(connects bottom and right)

7. T shape-1(connects all sides except top)

8. T shape-2(connects all sides except right)

9. T shape-3(connects all sides except down)

10. T shape-4(connects all sided except left)

11. ‘+’ shape (connects all 4 sides)



Pipes 1 and 2 can be obtained by rotating each other.

Pipes 3, 4, 5 and 6 can be obtained by rotating each other.

Pipes 7, 8, 9 and 10 can be obtained by rotating each other.



Input format:

T the number of test cases

For each test case, 1st line contains two integers N and M.

Then N lines follow each containing M integers.

Then integer A, at j-th position of i-th line represents a pipe shape as described above.

Output format:

Print an integer that is the correct answer followed by a new line.

Constraints

1 <= T <= 100

1 <= N, M <= 100

1 <= A <= 11 where A is the grid element.

Sample Input:

3

1 1

1

1 1

3

3 3

4 1 3

7 8 6

11 10 3

Sample Output:

0

-1

6






Explanation:

For Case 1 and Case 2: Since the grid has only one cell, the source is the left side of the cell and destination is its right side.

Case 1: Horizontal pipe connecting left and right side is given, thus the water flows left to right and no rotation is needed.

Case 2: L shaped pipe is given which can never be used to connect left and right sides irrespective of rotations, hence output is -1.

Case 3: The pipe at the top left (0,0) is rotated twice [ 4 -> 5 ] , the pipe at (1,0) is rotated once [ 7 -> 10 ] , the pipe at (1,1) is rotated once [ 8 -> 7 ] , the pipe at (1,2) is rotated once [ 6 -> 5] and the pipe at the right bottom (2,2) is rotated once [ 3 -> 4 ].

The minimum number of rotations is 2+1+1+1+1 = 6.