Gem Match Cascade

John plays a gem matching game a lot, and his scores are stuck. Write a program that finds the move clearing the most gems.

The board is a grid of colored gems, like this one:

BGR
GRR
BGY

A move swaps two gems that touch horizontally or vertically. Swapping the first two gems of the second row changes the board to this:

BGR
RGR
BGY

Whenever three or more gems of the same color end up in a row or a column, all of them vanish at once. In this example the three green gems vanish.

B.R
R.R
B.Y

One move can build several groups at once. Take this board:

RGOY
RGOG
OOYO
RGOG
YBOB

Swapping the rightmost orange gem of the middle row with the yellow gem next to it

RGOY
RGOG
OOOY
RGOG
YBOB

builds a row of three and a column of five, and all of them vanish.

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

Every gem sitting above an empty cell then falls until no empty cell is left below it.

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

Rows or columns of three or more that appear after the fall vanish as well.

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

This repeats until no row and no column holds three or more gems of the same color. The whole process is:

• Swap two touching gems.
• While some row or column holds three or more gems of the same color:
  • Remove those gems.
  • Drop gems until no gem sits above an empty cell.

In the real game, new gems drop in from the top to refill the board. Ignore that here.

The first line holds the number of test cases $T$. Each test case starts with a line holding two integers $N$ and $M$ separated by one space. The next $N$ lines each hold exactly $M$ uppercase letters, one letter per gem. Equal letters mean equal colors.

Limits

• Every gem character is an uppercase letter.
• The input board holds no row and no column with three or more consecutive gems of the same color.
• $1 \le T \le 100$
• $1 \le N \le 50$
• $1 \le M \le 50$

For each test case, print one line of the form Case #C: D, where $C$ is the test case number starting from 1 and $D$ is the largest number of gems a single swap can remove. If no two gems can be swapped, $D$ is 0.