벽 속의 또 다른 벽돌

오랜 세월 벽돌공으로 일해 온 당신은, 테트라드(Tetrad)사가 세운 여러 벽돌 벽의 구조적 안정성을 분석해 달라는 의뢰를 받았습니다. 테트라드사는 규격화된 벽돌 대신 기묘한 모양으로 만든 벽돌을 즐겨 사용합니다.

벽은 단위 칸으로 이루어진 격자이며, 모든 칸은 정확히 하나의 벽돌에 속합니다. 벽의 구조적 안정성은, 벽의 맨 위에서 맨 아래까지 이어지는 틈을 만들기 위해 제거해야 하는 벽돌의 최소 개수로 근사할 수 있습니다. 벽돌 하나를 제거하면 그 벽돌이 차지하던 칸이 모두 제거되어 틈의 일부가 됩니다. 테트라드사가 만든 여러 특이한 벽에 대해 이 최소 개수를 구하세요.

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $X$ ($1 \le X \le 100$)가 주어집니다. 각 데이터 집합은 두 부분으로 구성됩니다.

• M N 형식의 한 줄 ($1 \le M, N \le 20$). $M$과 $N$은 각각 벽의 높이와 너비(칸 단위)를 나타냅니다.
• 이어지는 $M$개의 줄. 각 줄은 정확히 $N$개의 대문자로 이루어집니다. 각 문자는 그 칸이 어느 벽돌에 속하는지를 나타냅니다. 모든 벽돌은 하나로 연결되어 있습니다. 즉, 한 벽돌의 각 칸은 같은 벽돌의 다른 칸과 상하좌우로 인접합니다(대각선은 인접으로 치지 않습니다). 서로 다른 벽돌이 같은 문자를 쓸 수도 있지만, 같은 문자를 쓰는 두 벽돌은 서로 인접하지 않습니다.

각 데이터 집합에 대해, 벽의 맨 윗줄의 어떤 칸에서 맨 아랫줄의 어떤 칸까지 이어지는 틈을 만들기 위해 제거해야 하는 벽돌의 최소 개수를 한 줄에 하나씩 출력하세요. 벽돌은 제자리에 고정되어 있으며, 아래의 벽돌이 제거되어도 떨어지지 않습니다. 틈은 제거된 칸들의 연결된 집합입니다. 즉, 틈을 이루는 각 칸은 틈의 다른 칸과 상하좌우로 인접해야 합니다(대각선은 인접으로 치지 않습니다).