Earth has been destroyed, and we humans emigrated to another planet, named Elth. On Elth, there exists many space-time tunnels connecting two portals at different location. If you wish, you can enter a tunnel from a portal, and you'll get out from the other portal of the space-time tunnel after 1 second. (Also you can just stay at the portal, nothing will happen.)

    Eland is working for EDA, a famous express delivery company on Elth. Today, he gets a task: delivering an important package to destination, as fast as possible. At first, Eland has a map of his city, which is a H*W matrix and marks his departure, destination and several portals of space-time tunnel. It costs 1 second for Eland to move up, down, left and right one grid. There are some grids in the map that Eland can't pass through because of the existence of monsters. 

    Of course, Eland can use space-time tunnels to make delivering faster. However, some tunnels are closed, the key to these tunnels are hiding in some other tunnels, when you go through(I think you know what is through) that tunnel with key, the closed tunnel will become available.

    Now, Eland gives you the map, and he knows which tunnels are available at first as well as the keys hiding in each tunnel. Can you help him calculating a best route for him to make the delivery?

    The first line of input file contains the total cases in the file.

    The first line of each case contains 3 integers: H, W, K, with 1 <= H, W <= 30, 0 <= K <= 10, representing the height of the map, the width of the map, and the number of tunnels, respectively.

    Then it follows H lines, each line contains a string of length W. These lines represent the map of Eland's city. In the map, 'X' means departure, 'Y' means destination, '#' means non-pass grid, and the top K upper alphabets represent these portals, each alphabet will occur twice, indicating the two ends of a tunnel.

    After the map, it follows a line showing the available tunnels at first. It will contain an integer N, with 0 <= N <= K, representing counts of available tunnels. Then it follows N upper alphabets, indicating these available tunnels in the map.

    At last, each case contains K lines, each line shows the keys hiding in the tunnel, the first line is tunnel A, the second line is tunnel B, and so on. In each line, it has an integer P, with 0 <= P <= K, and then following P upper alphabets, indicating these keys are hiding in the tunnel.