시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3929 823 506 19.073%

문제

상근이는 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+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzc0XHViYmY4IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjMWUwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWY0XHVjMWUwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7MCZxdW90O1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJlNGNcdWI1MjkgXHViYzE2XHVjNzNjXHViODVjIFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYjM4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YmIzOFx1Yzc0NCBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWMxZTBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDBcdWFjMWMsIDFcdWFjMWMsIFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzc0XHVhY2UwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNWY0XHVjMWUwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YzVmNFx1YzFlMFx1Yjg1YyBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3NTggXHVhYzFjXHVjMjE4XHViM2M0IDBcdWFjMWMsIDFcdWFjMWMsIFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzc0XHViMmU0LiBcdWM1ZjRcdWMxZTBcdWIyOTQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ2ZDRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWMxMWNcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktleXMiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gaXMgb24gYSBtaXNzaW9uIHRvIHN0ZWFsIHNvbWUgZG9jdW1lbnRzIG9mIGltcG9ydGFuY2UgZnJvbSBhIG9uZS1zdG9yeSBidWlsZGluZy4gSGUgaGFzIG1hbmFnZWQgdG8gZ2V0IGhvbGQgb2YgYSBkZXRhaWxlZCBcdWZiMDJvb3IgcGxhbiBvZiB0aGUgYnVpbGRpbmcsIGluZGljYXRpbmcgdGhlIGxvY2F0aW9ucyBvZiBhbGwgdGhlIGRvY3VtZW50cy4gVGhlcmUgYXJlIGRvb3JzIGluIHRoZSBidWlsZGluZyB0aGF0IHJlcXVpcmUgYSBrZXkgdG8gYmUgb3BlbmVkLiBKb2huIGhhcyBzb21lIGtleXMgaW4gaGlzIHBvc3Nlc3Npb24sIGFuZCB0aGVyZSBhcmUgc29tZSBrZXlzIGluIHRoZSBidWlsZGluZyBpdHNlbGYuIENhbiB5b3UgaGVscCBoaW0gXHVmYjAxZ3VyZSBvdXQgaG93IG1hbnkgZG9jdW1lbnRzIGhlIGNhbiBzdGVhbD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGggYW5kIHcgKDIgJmxlOyBoLCB3ICZsZTsgMTAwKTogdGhlIGhlaWdodCBhbmQgd2lkdGggb2YgdGhlIG1hcC48XC9saT5cclxuXHQ8bGk+aCBsaW5lcyB3aXRoIHcgY2hhcmFjdGVycyBkZXNjcmliaW5nIHRoZSBidWlsZGluZzpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+JnJzcXVvOy4mcnNxdW87IGlzIGFuIGVtcHR5IHNwYWNlLjxcL2xpPlxyXG5cdFx0PGxpPiZyc3F1bzsqJnJzcXVvOyBpcyBhbiBpbXBlbmV0cmFibGUgd2FsbC48XC9saT5cclxuXHRcdDxsaT4mcnNxdW87XFwkJnJzcXVvOyBpcyBhIGRvY3VtZW50IHRoYXQgSm9obiB3b3VsZCBsaWtlIHRvIHN0ZWFsLjxcL2xpPlxyXG5cdFx0PGxpPmFuIHVwcGVyY2FzZSBsZXR0ZXIgaXMgYSBkb29yLjxcL2xpPlxyXG5cdFx0PGxpPmEgbG93ZXJjYXNlIGxldHRlciBpcyBhIGtleSB0aGF0IG9wZW5zIGFsbCBkb29ycyBjb3JyZXNwb25kaW5nIHRvIGl0cyB1cHBlcmNhc2UgZXF1aXZhbGVudC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHN0cmluZyBjb25zaXN0aW5nIG9mIGRpc3RpbmN0IGxvd2VyY2FzZSBsZXR0ZXJzOiB0aGUga2V5cyB0aGF0IEpvaG4gaGFzIGluIGhpcyBwb3NzZXNzaW9uLiBJZiBoZSBoYXMgbm8ga2V5cywgdGhlIGxpbmUgY29udGFpbnMgJmxkcXVvOzAmcmRxdW87IGluc3RlYWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Sm9obiBjYW4gZnJlZWx5IG1vdmUgYXJvdW5kIHRoZSBvdXRzaWRlIG9mIHRoZSBidWlsZGluZy4gRm9yIGFueSBnaXZlbiBkb29yLCB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBrZXlzIHRoYXQgb3BlbiBpdCBjYW4gYmUgemVybywgb25lLCBvciBtb3JlIHRoYW4gb25lLiBGb3IgYW55IGdpdmVuIGtleSwgdGhlIG51bWJlciBvZiBkb29ycyB0aGF0IGl0IG9wZW5zIGNhbiBiZSB6ZXJvLCBvbmUgb3IgbW9yZSB0aGFuIG9uZS4gS2V5cyBjYW4gYmUgcmV1c2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyOiB0aGUgdG90YWwgbnVtYmVyIG9mIGRvY3VtZW50cyB0aGF0IEpvaG4gY2FuIHN0ZWFsLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d