다리 건설자들

왕은 다리가 건설되기를 원하며, 가능한 한 빨리 건설되기를 바란다. 왕은 N행 M열 격자 형태의 땅을 소유하고 있으며, 각 칸과 인접한 칸 사이에는 강이 흐른다. 왕은 모든 섬을 연결하기에 충분한 다리를 건설하는 데 몇 인시의 작업이 필요한지 당신이 알아내기를 원한다. 일부 칸은 실제로 호수이므로 그곳으로 다리를 건설할 필요가 없다.

섬 중 일부는 나무가 풍부한 숲이다. 왼쪽 위 모서리에는 베이스캠프가 있으며, 베이스캠프는 항상 숲이다.

두 섬이 수직 또는 수평으로 인접하고, 두 섬 중 하나가 이미 건설된 다리를 통해 베이스캠프에서 접근 가능한 경우에만 그 두 섬 사이에 다리를 건설할 수 있다.

다리를 건설하는 데 걸리는 인시는 건설자들이 가장 가까운 숲에서 다리를 건설하려는 섬까지 가기 위해 건너야 하는 다리의 수이며, 현재 건설 중인 다리도 포함한다. 건설자들은 두 섬 사이에 이미 다리가 있는 경우에만 그 사이를 걸어갈 수 있다.

왕은 이미 모든 섬을 연결할 방법이 적어도 하나는 있음을 보장했다.

섬의 지도가 주어질 때, 모든 섬을 연결하는 데 필요한 최소 인시를 출력하는 프로그램을 작성하라.

다음 예제를 살펴보자. 초록색 타일은 숲을, 회색 타일은 빈 섬을, 파란색 타일은 물을 나타낸다.

한 최적해는 먼저 베이스캠프의 숲에서 다음 다리들을 건설한다.

이 비용은 1 + 2 + 1 + 2 + 3 + 4 = 13이다.

이제 3행, 3열의 숲이 베이스캠프와 연결되었으므로, 그곳에서 다리를 건설할 수 있다. 한 최적해는 이 숲에서 건설한 다리들로 나머지 섬을 연결한다.

이 비용은 2 + 1 + 2 + 1 + 2 + 3 = 11이다. 따라서 총비용은 24이 되며, 이것이 최적해이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50 2 ≤ N ≤ 30 2 ≤ M ≤ 30 왼쪽 위 칸은 항상 'T'이다. 다리를 통해 모든 섬을 연결할 수 있다.

작은 데이터 세트 (테스트 세트 1 - 공개)

베이스캠프를 포함하여 격자에는 숲이 최대 2개 있다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

격자에 있는 숲의 수에는 제한이 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 행의 수 N과 열의 수 M이 공백으로 구분되어 한 줄에 주어지는 것으로 시작한다. 이어지는 N개의 줄에는 각각 정확히 M개의 문자가 주어진다. 'T'는 숲이 있는 섬을, '#'은 섬을, '.'은 물을 나타낸다.

"Case #X: Y"을 한 줄에 출력한다. 여기서 X는 1부터 세는 케이스 번호이고, Y는 모든 섬을 연결하는 데 필요한 최소 인시이다.