Problem B

As you know, mazes in some role-playing games are quite complicated. Usually, it should take a long time to keep trying different ways to get out of a maze. But here comes a question, that with the help of algorithm and computer, can we figure out a faster way to solve a maze?

So we are taking a experiment here. Now we have a maze in a shape of an N times M lattice (N rows and M columns). In the lattice, some grids are empty so that we may stand on them, while others are obstacles and it's forbidden to locate on these grids. In each move, we can make a move to the 8 adjacent empty grids with an exception: we cannot move through two obstacles' gap nor outside the maze. The following figure shows the moving rules.


Figure 1: Moving rules, in which white for empty grids and grey for obstacles


In order to get out of it, we need to trigger activations in the maze. Totally there are $K$ activations, each located on a specific empty grid. If we are standing on a grid with an activation, it will be triggered (and it disappears immediately). In the maze, our target is to trigger all $K$ activations in order. When the last activation is triggered, we may leave it at once.

Now we have already known the positions of obstacles and activations. Initially, we are standing on a specific grid in the maze. Can you figure out how many moves we should make at least to get out of it?

The number of test cases $T (T \leq 20)$ will occur in the first line of input.

For each test case:

The first line contains the number of rows $N (2 \leq N \leq 100)$, columns $M (2 \leq M \leq 100)$ and activations $K (1 \leq K \leq 10)$.

Each of the following $N$ lines contains $M$ characters, where a '#' denotes an obstacle and a '.' denotes an empty grid.

The following line contains the start position $(x, y)$, which denotes the grid on the $x$th row and the $y$th column. It's always an empty grid.

Each of the following $K$ lines describe a coordinate of the activations. All activations will not occur on obstacles, and two activations will not share the same grid. We need to trigger all of them in order of the given list.

For each test case, output the minimum moves we need to make to reach the target. If we cannot get out of the maze, output -1 instead.

3	
3 3 2
...
...
...
1 1
1 3
2 2
3 3 1
...
.#.
...
1 1
3 3
2 3 1
..#
.#.
1 1
2 3

3
3
-1

校第十六届大学生程序设计竞赛暨2016省赛集训队选拔赛