포탑 저격 (Small)

외계 침략자에게서 도시를 되찾는 전투가 끝났다. 도시는 $R$행 $C$열 격자로 나타낸다. 어떤 칸은 건물이고 나머지는 거리이다. 건물은 아무도 꿰뚫어 볼 수 없고, 뚫고 쏠 수 없고, 지나갈 수도 없다. 거리는 모두 볼 수 있고, 쏠 수 있고, 지나갈 수 있다.

물러난 침략자는 도시에 자동 경비 포탑을 남겨 두었다. 포탑은 모두 거리에 있고 건물 안에는 없다. 거리에는 병사도 있다. 처음에 병사와 포탑이 같은 칸에 있는 경우는 없다.

포탑은 움직이지 않는다. 크기가 작아서 시야도 사격도 막지 않는다. 병사는 살아 있는 포탑이 있는 칸으로는 들어갈 수 없지만, 그 포탑이 파괴된 뒤에는 그 칸을 지나갈 수 있다. 포탑은 가로나 세로로 시야가 닿는 칸에 있는 병사만 본다. 병사가 그런 칸으로 들어올 때 포탑은 쏘지 않는다. 그러나 병사가 그 칸에서 벗어나려고 하면, 들어온 뒤든 처음부터 그 칸에 있었든 포탑이 쏜다. 포탑은 사격을 움직임으로 보지 않으므로 병사는 그 칸에서 총을 쏠 수 있다. 그래서 죽는 병사는 없다. 최악의 경우에도 움직이지 않고 구조를 기다리면 된다.

병사는 각각 최대 $M$번 움직인다. 한 번의 이동은 가로나 세로로 인접한 한 칸으로 가는 것이다. 병사끼리는 서로 지나갈 수 있고, 다른 병사나 포탑의 시야를 막지 않는다. 병사에게는 총알이 한 발씩 있다. 가로나 세로로 시야가 닿는 곳에 포탑이 있으면 병사는 그 포탑을 쏘아 파괴할 수 있다. 한 발로 파괴하는 포탑은 하나뿐이다. 병사의 사격 솜씨가 뛰어나서, 총알은 시야에 놓인 다른 포탑이나 병사를 넘어 더 멀리 있는 포탑을 맞힌다.

병사와 포탑의 위치를 표시한 지도가 주어진다. 병사들이 파괴할 수 있는 포탑은 최대 몇 개인가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 지도의 너비 $C$, 지도의 높이 $R$, 병사 한 명이 움직일 수 있는 횟수 $M$이 주어진다. 다음 $R$개 줄에는 각각 $C$개의 문자가 주어진다. .은 거리, #은 건물, S는 병사, T는 포탑이다.

제한

• $1 \le T \le 100$
• $0 \le M < C \times R$
• $1 \le C \le 30$
• $1 \le R \le 30$
• S의 개수는 1개 이상 10개 이하이다.
• T의 개수는 1개 이상 10개 이하이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 파괴할 수 있는 포탑의 최대 개수이다.

아래 설명에서는 병사와 포탑에 각각 1번부터 번호를 붙인다. 번호는 맨 윗줄부터 아래로 내려가며 각 줄에서는 왼쪽부터 오른쪽으로 읽는 순서를 따르고, 병사의 번호와 포탑의 번호는 서로 별개이다.

두 번째 예제에서는 3번 병사가 위로 세 칸 움직여 3번 포탑을 파괴한다. 이어서 1번 병사가 위로 한 칸, 오른쪽으로 한 칸 움직여 3번 포탑이 있던 자리로 간 다음, 2번 포탑을 넘겨 쏘아 1번 포탑을 파괴한다. 마지막으로 2번 병사가 위로 세 칸 움직여 2번 포탑을 파괴한다. 세 포탑이 모두 무너진다.

세 번째 예제에서는 1번 병사가 위로 한 칸, 오른쪽으로 세 칸 움직여 2번 포탑을 파괴한다. 2번 병사가 위로 한 칸, 오른쪽으로 세 칸 움직여 1번 포탑을 파괴한다. 6번 병사가 아래로 한 칸, 오른쪽으로 세 칸 움직여 3번 포탑을 파괴한다. 나머지 병사는 이동 횟수가 모자라 어떤 포탑도 쏘지 못한다.

네 번째 예제에서는 병사가 포탑과 같은 행이나 같은 열에 있는 칸으로 갈 수 없어서 포탑을 파괴하지 못한다.