포탑 파괴 (라지)

침략자와의 전쟁이 끝나고 도시는 다시 자유를 찾았다.

도시는 $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 100$
• $1 \le R \le 100$
• S의 개수는 1개 이상 100개 이하다
• T의 개수는 1개 이상 100개 이하다

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 세는 테스트 케이스 번호이고, $y$는 병사들이 파괴할 수 있는 포탑의 최대 개수다. 다른 것은 출력하지 않는다. 이동과 사격의 구체적인 계획은 출력에 포함하지 않는다.

예제의 첫 번째 케이스에서는 병사가 아래로 한 칸 내려간 다음 아랫줄을 따라 쏘면 된다.

두 번째 케이스에서는 병사 셋이 왼쪽 열에, 포탑 셋이 오른쪽 열에 서 있다. 맨 아래 병사가 위로 세 칸 올라가 맨 아래 포탑을 파괴한다. 그 포탑이 있던 칸이 비었으므로, 맨 위 병사가 위로 한 칸 올라간 다음 오른쪽으로 한 칸 옮겨 그 칸에 서고, 오른쪽 열을 따라 가운데 포탑 너머의 맨 위 포탑을 맞힌다. 남은 병사가 위로 세 칸 올라가 가운데 포탑을 파괴한다. 순서가 중요하다. 맨 아래 포탑이 살아 있는 동안에는 그 포탑이 감시하는 칸에 들어간 병사가 다시는 움직이지 못한다.

세 번째 케이스에서는 가운데 열의 건물 때문에 모든 병사가 맨 윗줄이나 맨 아랫줄로 돌아가야 한다. 네 번 이동해서 병사 한 명이 넷째 열의 포탑이 보이는 칸에 닿고, 병사 두 명이 다섯째 열의 포탑 셋이 보이는 칸에 닿는다. 병사마다 총알이 한 발이므로 포탑 셋이 파괴되고 하나가 남는다.

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