보석 맞추기 연쇄

민수는 요즘 보석 맞추기 게임을 자주 하는데 점수가 좀처럼 오르지 않는다. 한 수로 보석을 가장 많이 없애는 방법을 찾아 주자.

게임판은 여러 색의 보석이 격자로 놓인 모양이다. 예를 들면 다음과 같다.

BGR
GRR
BGY

한 수는 가로나 세로로 맞닿은 두 보석을 맞바꾸는 것이다. 위 판에서 둘째 줄의 앞 두 보석을 맞바꾸면 판이 이렇게 바뀐다.

BGR
RGR
BGY

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

B.R
R.R
B.Y

한 수로 세 개 이상짜리 묶음이 여러 개 만들어지기도 한다. 다음 판을 보자.

RGOY
RGOG
OOYO
RGOG
YBOB

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

RGOY
RGOG
OOOY
RGOG
YBOB

가로 세 개와 세로 다섯 개가 동시에 만들어지고, 이 보석이 모두 사라진다.

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

그다음 빈칸 위에 있던 보석은 아래에 빈칸이 남지 않을 때까지 떨어진다.

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

떨어진 뒤에 새로 만들어진 세 개 이상짜리 줄도 다시 사라진다.

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

같은 색 보석이 세 개 이상 연달아 놓인 가로줄이나 세로줄이 더 이상 없을 때까지 이 과정이 이어진다. 정리하면 다음과 같다.

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

실제 게임에서는 사라진 자리를 위에서 내려온 새 보석이 채우지만, 이 문제에서는 그것을 생각하지 않는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $M$이 공백 하나를 사이에 두고 주어진다. 이어지는 $N$개의 줄에는 각각 대문자가 정확히 $M$개 주어지며, 문자 하나가 보석 하나를 나타낸다. 문자가 같으면 색도 같다.

제한

• 보석을 나타내는 문자는 모두 대문자다.
• 입력으로 주어지는 판에는 같은 색 보석이 세 개 이상 연달아 놓인 가로줄이나 세로줄이 없다.
• $1 \le T \le 100$
• $1 \le N \le 50$
• $1 \le M \le 50$

각 테스트 케이스마다 Case #C: D 형식으로 한 줄을 출력한다. $C$는 1부터 시작하는 테스트 케이스 번호이고, $D$는 한 번의 맞바꾸기로 없앨 수 있는 보석 개수의 최댓값이다. 맞바꿀 수 있는 두 보석이 없으면 $D$는 0이다.