The kingdom of Azkaroth is in great danger. Some strange creatures have captured the city and attacking the poor inhabitants.

The old wise king has chosen his best knights to save the kingdom from these creatures. They have already found that the creatures are targeting some food mills. So, the best way is to send the knights to look after the food mills. And if anything goes wrong he may call others to attack the creatures.

The kingdom can be modeled as an n x n grid. The legends are:

A knight can go to a mill using some moves, in each move a knight can go to its four neighboring cells {North, East, West, South} with the restriction that the destination cell shouldn't contain a rock (multiple knights can move together in a cell). And the number of mills that can be maintained by a knight is limited. The cost to look after a mill by a knight is the distance between the knight and the mill, distance means the number of moves the knight has to use to go to the mill. If a knight looks after multiple mills, the cost is the summation of distances from the knight to the mills.

Now your task is to find the minimum total cost needed for the knights to look after all the mills. There can be more than one knight looking after a mill.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing three integers n (5 ≤ n ≤ 30), k (1 ≤ k ≤ 26) and m (1 ≤ m ≤ 100) where k denotes the number of knights and m denotes the number of mills in the grid. The knights will be marked by first k capital letters and the grid contains exactly one letter of each kind. Each of the next n lines contains n characters denoting the grid.

The next line contains k space separated integers (between 1 and 100) denoting the number of mills the i^th knight can look after. That means the first integer denotes the number of mills that can be looked after by knight 'A', second integer denotes the number of mills looked after by knight 'B' and so on. And the outer cells of the grid will be rocks.

For each case, print the case number and the minimum cost as described above. You can assume that a solution will always exist.