시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 7543 1945 1188 23.285%

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

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

입력

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

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

  • '.'는 빈 공간을 나타낸다.
  • '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • '\$'는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공간이나 문을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

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

예제 입력 1

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

예제 출력 1

3
1
0
W3sicHJvYmxlbV9pZCI6IjkzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWMxZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCZuYnNwOzFcdWNlMzUgXHViZTRjXHViNTI5XHVjNWQwIFx1Y2U2OFx1Yzc4NVx1ZDU3NCBcdWI5ZTRcdWM2YjAgXHVjOTExXHVjNjk0XHVkNTVjIFx1YmIzOFx1YzExY1x1Yjk3YyBcdWQ2ZDRcdWNjZDBcdWM2MjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQzYzlcdWJhNzRcdWIzYzRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjMTFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWJhYThcdWI0NTAgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gXHViZTRjXHViNTI5XHVjNzU4IFx1YmIzOFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjN2EwXHVhY2E4XHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYjM4XHVjNzQ0IFx1YzVmNFx1YjgyNFx1YmE3NCBcdWM1ZjRcdWMxZTBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzdjXHViZDgwIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjNzdjXHViZDgwIFx1YzVmNFx1YzFlMFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NTggXHViYzE0XHViMmU1XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ2ZDRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWMxMWNcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YjI5NCAxMDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWIzYzRcdWM3NTggXHViMTkyXHVjNzc0XHVjNjQwIFx1YjEwOFx1YmU0NCBoXHVjNjQwIHcgKDIgJmxlOyBoLCB3ICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBoXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHdcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+JiMzOTsqJiMzOTtcdWIyOTQgXHViY2JkXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmNiZFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+JiMzOTtcXCQmIzM5O1x1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkNmQ0XHVjY2QwXHVjNTdjXHVkNTU4XHViMjk0IFx1YmIzOFx1YzExY1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWJiMzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViMjk0IFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YWRmOCBcdWJiMzhcdWM3OTBcdWM3NTggXHViMzAwXHViYjM4XHVjNzkwXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3NDQgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzc0XHViYmY4IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjMWUwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWY0XHVjMWUwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7MCZxdW90O1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgXHViZTRjXHViNTI5XHVjNzU4IFx1YmMxNlx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmU0Y1x1YjUyOSBcdWFjMDBcdWM3YTVcdWM3OTBcdWI5YWNcdWM3NTggXHViZTQ4IFx1YWNmNVx1YWMwNFx1Yzc3NFx1YjA5OCBcdWJiMzhcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YmU0Y1x1YjUyOSBcdWM1NDhcdWQzMGVcdWM3NDQgXHViNGRjXHViMDk4XHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJiMzhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkZjggXHViYjM4XHVjNzQ0IFx1YzVmNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmNFx1YzFlMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMFx1YWMxYywgMVx1YWMxYywgXHViNjEwXHViMjk0IFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NzRcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkZjggXHVjNWY0XHVjMWUwXHViODVjIFx1YzVmNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIzYzQgMFx1YWMxYywgMVx1YWMxYywgXHViNjEwXHViMjk0IFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NzRcdWIyZTQuIFx1YzVmNFx1YzFlMFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1ZDZkNFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1YzExY1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS2V5cyIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obiBpcyBvbiBhIG1pc3Npb24gdG8gc3RlYWwgc29tZSBkb2N1bWVudHMgb2YgaW1wb3J0YW5jZSBmcm9tIGEgb25lLXN0b3J5IGJ1aWxkaW5nLiBIZSBoYXMgbWFuYWdlZCB0byBnZXQgaG9sZCBvZiBhIGRldGFpbGVkIFx1ZmIwMm9vciBwbGFuIG9mIHRoZSBidWlsZGluZywgaW5kaWNhdGluZyB0aGUgbG9jYXRpb25zIG9mIGFsbCB0aGUgZG9jdW1lbnRzLiBUaGVyZSBhcmUgZG9vcnMgaW4gdGhlIGJ1aWxkaW5nIHRoYXQgcmVxdWlyZSBhIGtleSB0byBiZSBvcGVuZWQuIEpvaG4gaGFzIHNvbWUga2V5cyBpbiBoaXMgcG9zc2Vzc2lvbiwgYW5kIHRoZXJlIGFyZSBzb21lIGtleXMgaW4gdGhlIGJ1aWxkaW5nIGl0c2VsZi4gQ2FuIHlvdSBoZWxwIGhpbSBcdWZiMDFndXJlIG91dCBob3cgbWFueSBkb2N1bWVudHMgaGUgY2FuIHN0ZWFsPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgaCBhbmQgdyAoMiAmbGU7IGgsIHcgJmxlOyAxMDApOiB0aGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiB0aGUgbWFwLjxcL2xpPlxyXG5cdDxsaT5oIGxpbmVzIHdpdGggdyBjaGFyYWN0ZXJzIGRlc2NyaWJpbmcgdGhlIGJ1aWxkaW5nOlxyXG5cdDx1bD5cclxuXHRcdDxsaT4mcnNxdW87LiZyc3F1bzsgaXMgYW4gZW1wdHkgc3BhY2UuPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvOyomcnNxdW87IGlzIGFuIGltcGVuZXRyYWJsZSB3YWxsLjxcL2xpPlxyXG5cdFx0PGxpPiZyc3F1bztcXCQmcnNxdW87IGlzIGEgZG9jdW1lbnQgdGhhdCBKb2huIHdvdWxkIGxpa2UgdG8gc3RlYWwuPFwvbGk+XHJcblx0XHQ8bGk+YW4gdXBwZXJjYXNlIGxldHRlciBpcyBhIGRvb3IuPFwvbGk+XHJcblx0XHQ8bGk+YSBsb3dlcmNhc2UgbGV0dGVyIGlzIGEga2V5IHRoYXQgb3BlbnMgYWxsIGRvb3JzIGNvcnJlc3BvbmRpbmcgdG8gaXRzIHVwcGVyY2FzZSBlcXVpdmFsZW50LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc3RyaW5nIGNvbnNpc3Rpbmcgb2YgZGlzdGluY3QgbG93ZXJjYXNlIGxldHRlcnM6IHRoZSBrZXlzIHRoYXQgSm9obiBoYXMgaW4gaGlzIHBvc3Nlc3Npb24uIElmIGhlIGhhcyBubyBrZXlzLCB0aGUgbGluZSBjb250YWlucyAmbGRxdW87MCZyZHF1bzsgaW5zdGVhZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Kb2huIGNhbiBmcmVlbHkgbW92ZSBhcm91bmQgdGhlIG91dHNpZGUgb2YgdGhlIGJ1aWxkaW5nLiBGb3IgYW55IGdpdmVuIGRvb3IsIHRoZSBudW1iZXIgb2YgYXZhaWxhYmxlIGtleXMgdGhhdCBvcGVuIGl0IGNhbiBiZSB6ZXJvLCBvbmUsIG9yIG1vcmUgdGhhbiBvbmUuIEZvciBhbnkgZ2l2ZW4ga2V5LCB0aGUgbnVtYmVyIG9mIGRvb3JzIHRoYXQgaXQgb3BlbnMgY2FuIGJlIHplcm8sIG9uZSBvciBtb3JlIHRoYW4gb25lLiBLZXlzIGNhbiBiZSByZXVzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSB0b3RhbCBudW1iZXIgb2YgZG9jdW1lbnRzIHRoYXQgSm9obiBjYW4gc3RlYWwuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=