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,r20<=c1,c2
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

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0