Another Brick in the Wall

After years as a brick-layer, you have been called upon to analyze the structural integrity of various brick walls built by the Tetrad Corporation. Instead of using regular-sized bricks, the Tetrad Corporation seems overly fond of bricks made out of strange shapes.

A wall is a grid of unit cells, and every cell belongs to exactly one brick. The structural integrity of a wall can be approximated by the fewest number of bricks that must be removed to create a gap running from the top of the wall to the bottom. Removing a brick removes all of the cells it occupies, and those cells become part of the gap. Determine that minimum number for various odd walls created by Tetrad.

The first line contains a single integer $X$ ($1 \le X \le 100$), the number of data sets. Each data set consists of two parts:

• A line M N ($1 \le M, N \le 20$), where $M$ and $N$ are the height and width (in cells) of the wall, respectively.
• $M$ lines that follow, each exactly $N$ uppercase letters long. Each letter indicates which brick that cell belongs to. Every brick is contiguous: each cell of a brick is adjacent (up, down, left, or right; diagonals do not count) to another cell of the same brick. Different bricks may reuse the same letter, but two bricks that use the same letter are never adjacent to each other.

For each data set, output on its own line the fewest number of bricks that must be removed to create a gap leading from some cell in the top row of the wall to some cell in the bottom row. Bricks stay fixed in place and do not fall when bricks beneath them are removed. A gap is a set of removed cells that is connected: each cell of the gap must be adjacent (diagonals do not count) to another cell of the gap.