Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3847
Collect Chars

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Bob was playing MC and was punished by Alice. Bob was trapped in a maze and there were some characters on some specific cells. When he walks on a specific point, he will pick up the character automatically (he cannot refuse to do that) and push back the character in his bag (You can treat it as adding a character to the end of a string and initially, the string is empty.). Alice has set several goal strings and when Bob's bag contains any one of the strings, Bob is enabled to return to the true world.

Bob can walk to the adjacent cell (up, down, left, right) at one time, and it costs no time to pick up the character and the character won't disappear, which means if Bob want's he can get endless characters once he walked on the certain cell but he must pick up at least one character.

Bob wants to leave the maze as soon as possible, and he asks you for the shortest time that he can go out of that maze.

#### Input

The first line is an integer n, indicating the number of testcases.

In each case, the first line is two integers L and C (0 < L, C ≤ 20). After this, L lines follow, and each has C characters. For each character, '.' stands for an open space, '#' stands for a wall which cannot be crossed, '@' stands for the beginning point of the maze. All capital letters 'A' to 'Z' stand for the characters which can be picked up.

After that, there is one integer W, which means the number of goal strings (0 < W ≤ 200). And W lines following, each line has a string, containing letters 'A' to 'Z' only, which length is less than 100.

#### Output

For each case, you should output an integer. The answer is the minimum time that Bob must use to get out of the maze. If he can't do that, you should output -1.

```2
5 5
A.DB#
@#.##
.#..C
.#...
.....
3
AB
AC
BC
5 5
A.DB#
@#.##
.#..C
.#...
.....
2
AC
```

```11
9
```

#### Hint

In the first sample, Bob will get "AC" as for goal string. And in the second sample, Bob will get "AADBBBDCC" as for goal string.

Author: Ni, Xinyi
Source: ZOJ Monthly, January 2015
Submit    Status