다리 건설 (작은 버전)

왕은 다리를 최대한 빨리 놓고 싶다. 왕의 땅은 $N$행 $M$열 격자이고, 인접한 두 칸 사이에는 강이 흐른다. 어떤 칸은 호수라서 다리를 놓을 필요가 없다. 호수가 아닌 칸은 모두 섬이다. 모든 섬을 잇는 데 드는 최소 인시를 구해야 한다.

섬 중 일부는 나무가 많은 숲이다. 왼쪽 위 칸은 항상 숲이고, 이 칸을 기지라고 한다.

다리는 위아래나 좌우로 인접한 두 섬 사이에만 놓을 수 있고, 그 두 섬 중 하나는 이미 놓인 다리로 기지와 이어져 있어야 한다.

다리 하나를 놓는 데 드는 인시는 가장 가까운 숲에서 다리를 놓을 섬까지 가는 동안 건너는 다리의 수이고, 지금 놓는 다리도 센다. 인부는 다리가 이미 놓인 두 섬 사이만 걸어서 지나갈 수 있다. 그래서 어떤 숲은 기지와 이어진 뒤부터 출발점으로 쓸 수 있다.

모든 섬을 잇는 방법이 적어도 하나 있다는 것은 왕이 미리 확인해 두었다.

다음 예를 보자. 초록색은 숲, 회색은 숲이 아닌 섬, 파란색은 물이다.

최적해 하나는 기지에서 다음 다리부터 놓는다.

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

이제 3행 3열의 숲이 기지와 이어졌으므로 그 숲에서도 다리를 놓을 수 있다. 남은 섬은 이 숲에서 놓은 다리로 잇는다.

여기에 드는 인시는 $2 + 1 + 2 + 1 + 2 + 3 = 11$이다. 합은 24이고, 이보다 적게 드는 방법은 없다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 행의 수 $N$과 열의 수 $M$이 공백으로 구분되어 주어진다. 다음 $N$개의 줄에는 각각 정확히 $M$개의 문자가 주어진다. 'T'는 숲이 있는 섬, '#'은 숲이 없는 섬, '.'은 물이다.

제한

• $1 \le T \le 50$
• $2 \le N \le 30$
• $2 \le M \le 30$
• 왼쪽 위 칸은 항상 'T'이다.
• 모든 섬을 다리로 잇는 방법이 존재한다.
• 격자에 있는 숲은 기지를 포함해 최대 2개이다.

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