Bejeweled Befuddlement (Small1)

John plays Bejeweled and wants a program that tells him how much a single move clears.

The board is a grid of gems. Each gem is one uppercase letter, and gems written with the same letter have the same color.

BGR
GRR
BGY

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

BGR
RGR
BGY

Whenever three or more gems of the same color stand next to each other along a row or along a column, all of them vanish at once. Here the three green gems vanish. A dot marks an empty cell.

B.R
R.R
B.Y

Several groups can vanish together. Take this board.

RGOY
RGOG
OOYO
RGOG
YBOB

Swap the rightmost orange gem of the middle row with the yellow gem beside it.

RGOY
RGOG
OOOY
RGOG
YBOB

That makes a row of 3 and a column of 5, and every gem in them vanishes.

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

Every gem that sits above an empty cell then falls down.

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

Groups of three or more formed by 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 in a stretch. The whole process is:

• Swap two gems.
• While some row or column holds three or more gems of the same color in a stretch:
  • Remove those gems.
  • Move every gem that has an empty cell below it down, until no gem sits above an empty cell.

In the real game new gems drop in from the top to replace the removed ones. Ignore that here: the top of a column stays empty.

Given a board, report the largest number of gems that one swap can remove.

The first line has the number of test cases $T$. Each test case starts with a line holding two integers $N$ and $M$ separated by a space. The next $N$ lines each hold exactly $M$ uppercase letters, one letter per gem. Gems written with the same letter have the same color.

Limits

• Every gem character is an uppercase letter.
• The input board has no stretch of three or more gems of the same color along a row or along a column.
• $1 \le T \le 20$
• $3 \le N \le 10$
• $3 \le M \le 10$

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 that one swap can remove. If no swap removes a gem, $D$ is 0.