Under construction

Still being built. Things may change

Keys

Time limit1sMemory limit256 MB

Summary
Enter the grid from any open border cell, pick up keys to open matching doors, and collect the most reachable documents.
Level

Medium5 of 10

Topics
BFS, Simulation
Solved
No attempts yet

Problem

Sanggeun wants to break into a single storey building and steal the important documents inside. The floor plan he carries marks the position of every document. Every door in the building is locked, so opening one takes a key. He already holds some of the keys, and other keys are lying on the floor of the building. Sanggeun moves only up, down, left, and right.

Write a program that finds the largest number of documents Sanggeun can steal.

Input

The first line contains the number of test cases. There are at most 100 test cases.

The first line of each test case contains the height and the width of the map, hh and ww (2≤h,w≤1002 \le h, w \le 100). The next hh lines contain ww characters each, describing the building. Every character is one of the following.

  • . is an empty space.
  • * is a wall, and Sanggeun cannot pass through it.
  • $ is a document Sanggeun has to steal.
  • An uppercase letter is a door.
  • A lowercase letter is a key, and it opens every door marked with the uppercase form of that letter.

The last line contains the keys Sanggeun already holds, written without spaces. If he holds no key at all, the line is 0.

Sanggeun starts outside the building and enters or leaves it through any cell on the border of the map that is not a wall. The number of keys that open a given door is 0, 1, or more, and the number of doors a given key opens is also 0, 1, or more. A key can be used any number of times.

Output

For each test case, print the largest number of documents Sanggeun can steal, one per line.

Examples1

  1. Example 1

    Input
    3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony
    Expected output
    3
1
0