보석 퍼즐의 한 수 (Small1)

존은 보석 맞추기 게임을 하면서 한 수로 얼마나 많은 보석을 없앨 수 있는지 알려주는 프로그램을 원한다.

게임판은 보석이 놓인 격자다. 보석 하나는 대문자 한 글자로 적고, 같은 글자로 적힌 보석은 같은 색이다.

BGR
GRR
BGY

한 수는 가로나 세로로 맞닿은 보석 두 개를 맞바꾸는 것이다. 둘째 줄의 앞쪽 보석 두 개를 맞바꾸면 판이 이렇게 된다.

BGR
RGR
BGY

이때 같은 색 보석이 가로나 세로로 3개 이상 연달아 놓이면 그 보석은 모두 한꺼번에 사라진다. 이 예에서는 초록 보석 3개가 사라진다. 빈칸은 마침표로 적는다.

B.R
R.R
B.Y

여러 묶음이 한꺼번에 사라지기도 한다. 다음 판을 보자.

RGOY
RGOG
OOYO
RGOG
YBOB

가운데 줄에서 가장 오른쪽 주황 보석과 그 옆의 노랑 보석을 맞바꾼다.

RGOY
RGOG
OOOY
RGOG
YBOB

가로 3개와 세로 5개가 만들어지고, 여기에 속한 보석이 모두 사라진다.

RG.Y
RG.G
...Y
RG.G
YB.B

그다음 빈칸 위에 있던 보석이 아래로 떨어진다.

...Y
RG.G
RG.Y
RG.G
YB.B

떨어지면서 새로 만들어진 3개 이상의 묶음도 사라진다.

...Y
...G
...Y
...G
YB.B

같은 색 보석이 3개 이상 연달아 놓인 가로줄이나 세로줄이 없어질 때까지 이 과정을 반복한다. 전체 과정을 정리하면 다음과 같다.

• 보석 두 개를 맞바꾼다.
• 같은 색 보석이 3개 이상 연달아 놓인 가로줄이나 세로줄이 있는 동안 다음을 반복한다.
  • 그 보석을 모두 없앤다.
  • 빈칸 위에 보석이 남지 않을 때까지, 아래가 빈칸인 보석을 아래로 내린다.

실제 게임에서는 없어진 자리에 위에서 새 보석이 떨어져 들어오지만, 이 문제에서는 그런 일이 없다. 각 열의 위쪽은 빈칸으로 남는다.

게임판이 주어지면, 한 번의 맞바꾸기로 없앨 수 있는 보석 개수의 최댓값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. 이어지는 $N$개 줄에는 각각 대문자 $M$개가 주어지고, 한 글자가 보석 하나를 나타낸다. 같은 글자로 적힌 보석은 같은 색이다.

제한

• 보석을 나타내는 문자는 모두 대문자다.
• 입력 판에는 같은 색 보석이 가로나 세로로 3개 이상 연달아 놓인 곳이 없다.
• $1 \le T \le 20$
• $3 \le N \le 10$
• $3 \le M \le 10$

각 테스트 케이스마다 Case #C: D 꼴로 한 줄씩 출력한다. $C$는 1부터 시작하는 테스트 케이스 번호이고, $D$는 한 번의 맞바꾸기로 없앨 수 있는 보석 개수의 최댓값이다. 어떤 맞바꾸기로도 보석이 사라지지 않으면 $D$는 0이다.