다리 건설 (라지)

왕은 다리를 놓고 싶어 하고, 되도록 빨리 놓고 싶어 한다. 왕의 땅은 $N \times M$ 격자다. 인접한 두 칸 사이에는 강이 흘러서 칸마다 서로 떨어져 있다. 각 칸은 섬이거나 호수이고, 호수에는 다리를 놓지 않아도 된다.

섬 중 일부는 나무가 많은 숲이다. 왼쪽 위 칸은 베이스캠프이고, 이 칸은 항상 숲이다.

다리는 세로나 가로로 인접한 두 섬 사이에만 놓을 수 있다. 또 두 섬 중 하나는 이미 놓인 다리를 따라 베이스캠프에서 갈 수 있어야 한다.

다리 하나를 놓는 데 드는 인시(man-hour)는 가장 가까운 숲에서 출발해 다리를 놓을 섬까지 건너야 하는 다리의 수이고, 지금 놓는 다리도 센다. 인부는 다리가 이미 놓인 두 섬 사이만 걸어서 건넌다.

왕은 모든 섬을 연결하는 방법이 적어도 하나 있도록 미리 준비해 두었다. 지도가 주어질 때 모든 섬을 연결하는 데 드는 최소 인시를 구하라.

다음 지도를 보자. 초록색 칸은 숲, 회색 칸은 나무가 없는 섬, 파란색 칸은 물이다.

최적해 하나는 베이스캠프의 숲에서 다음 다리부터 놓는다.

여기에 드는 인시는 $1 + 2 + 1 + 2 + 3 + 4 = 13$이다.

이제 3행 3열의 숲이 베이스캠프와 이어졌으므로 그 숲에서도 다리를 놓을 수 있다. 최적해 하나는 남은 섬을 그 숲에서 놓은 다리로 잇는다.

여기에 드는 인시는 $2 + 1 + 2 + 1 + 2 + 3 = 11$이다. 전체 인시는 24이고, 이 값이 최솟값이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 행의 수 $N$과 열의 수 $M$이 공백을 두고 주어진다. 이어지는 $N$개의 줄에는 각각 정확히 $M$개의 문자가 주어진다. T는 숲이 있는 섬, #은 나무가 없는 섬, .은 물이다.

제한

• $1 \le T \le 50$
• $2 \le N \le 30$
• $2 \le M \le 30$
• 왼쪽 위 칸은 항상 T다.
• 모든 섬을 다리로 연결하는 방법이 항상 존재한다.
• 격자에 있는 숲의 개수에는 제한이 없다.

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 모든 섬을 연결하는 데 드는 최소 인시다.