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