열쇠

상근이는 단층 건물에 침입해 중요한 문서를 훔치려고 한다. 상근이가 가진 평면도에는 문서의 위치가 모두 표시되어 있다. 건물의 문은 전부 잠겨 있어서 문을 열려면 열쇠가 필요하다. 상근이가 이미 손에 쥔 열쇠도 있고, 건물 바닥에 떨어져 있는 열쇠도 있다. 상근이는 상하좌우로만 움직인다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 $h$, $w$ ($2 \le h, w \le 100$)가 주어진다. 다음 $h$개 줄에는 건물을 나타내는 문자가 한 줄에 $w$개씩 주어지며, 각 문자는 다음 중 하나이다.

• .는 빈 공간이다.
• *는 벽이고, 상근이는 벽을 지나갈 수 없다.
• $는 상근이가 훔쳐야 하는 문서이다.
• 알파벳 대문자는 문이다.
• 알파벳 소문자는 열쇠이고, 같은 알파벳의 대문자로 표시된 문을 모두 열 수 있다.

마지막 줄에는 상근이가 이미 가진 열쇠가 공백 없이 주어진다. 열쇠를 하나도 가지고 있지 않으면 0이 주어진다.

상근이는 처음에 건물 밖에 있고, 지도 가장자리에서 벽이 아닌 칸으로 건물을 드나든다. 문 하나를 열 수 있는 열쇠는 0개일 수도, 1개일 수도, 그보다 많을 수도 있다. 열쇠 하나로 열 수 있는 문의 개수도 마찬가지다. 열쇠는 여러 번 써도 된다.

각 테스트 케이스마다 상근이가 훔칠 수 있는 문서의 최대 개수를 한 줄에 하나씩 출력한다.