John is on a mission to steal some documents of importance from a one-story building. He has managed to get hold of a detailed floor plan of the building, indicating the locations of all the documents. There are doors in the building that require a key to be opened. John has some keys in his possession, and there are some keys in the building itself. Can you help him figure out how many documents he can steal? \textbf{nput} On the first line one positive number: the number of test cases, at most \textbf{100}. After that per test case: \begin{itemize} \item one line with two space-separated integers \textbf{h} and \textbf{w} (\textbf{2} ≤ \textbf{h}, \textbf{w} ≤ \textbf{100}): the height and width of the map. \item \textbf{h} lines with \textbf{w} characters describing the building: \begin{itemize} \item '\textbf{.}' is an empty space. \item '\textbf{*}' is an impenetrable wall. \item '\textbf{\$}' is a document that John would like to steal. \item an uppercase letter is a door. \item a lowercase letter is a key that opens all doors corresponding to its uppercase equivalent. \end{itemize} \item one line with a string consisting of distinct lowercase letters: the keys that John has in his possession. If he has no keys, the line contains "\textbf{0}" instead. \end{itemize} John can freely move around the outside of the building. For any given door, the number of available keys that open it can be zero, one, or more than one. For any given key, the number of doors that it opens can be zero, one or more than one. Keys can be reused. \OutputFile For each test case print one line with an integer: the total number of documents that John can steal.