# Maze Game

This time we are going to play a Number Game.

The game is played on an

`R x C`

board; rows are numbered 0 to R - 1 from top to bottom and columns are numbered 0 to C - 1 from left to right. The cell in row r and column c is said to have coordinates (r, c). Each cell of the board either contains a single-digit number (0 to 9) or is empty.
The board is given as R x C character array where the j-th character of the i-th element represents the cell at row i and column j; this element is a digit character ('0' - '9') if the cell contains the respective single-digit number or '.' if the cell is empty.

The goal of the game is to get from cell

`(r1, c1)`

to cell `(r2, c2)`

with the fewest number of moves. A move is a jump of length d in a horizontal or vertical direction from a cell with a number d; more formally, if your position is (r, c) and the cell contains a number d, you can move to cell (r - d, c), (r + d, c), (r, c - d), or (r, c + d). Note that an empty cell or a cell with number 0 is a dead-end. You are also not allowed to leave the board at any time.
Furthermore, before performing moves you are allowed to write any single-digit numbers in at most

`K`

empty cells.
**Input**

First Line contains denoting number of test cases.

Each test case begins with two integers on one line denoting R and C respectively.

Next R lines contains description of board each containing C characters.

Next Line contains 5 Integers denoting r1,c1,r2,c2 and K respectively.

**Output**

Every Test cases gives the minimum number of moves required to do this if it is possible and print -1 instead.

**Constraints**

T=111

1<=R,C<=50

0<=K<=50

0<=r1,r2

**Sample Input**

```
```

2

3 4

...2

....

3...

0 0 2 3 0

3 4

...2

....

3...

0 0 2 3 1

**Sample Output**

```
```

-1

2

*Problem Setter : Arjun Singh Bhatia*

**Languages:**Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text