Bridge Builders (Small)

The king wants bridges built, and he wants them built as quickly as possible. His land is an $N$ by $M$ grid of cells, and a river runs between every pair of adjacent cells. Some cells are lakes, so no bridge has to reach them. Every other cell is an island. Compute the smallest number of man-hours needed to connect all islands.

Some islands are forests where trees are abundant. The top left cell is always a forest, and that cell is the base camp.

A bridge can be built only between two islands that are vertically or horizontally adjacent, and one of those two islands must already be connected to the base camp by bridges that are built.

The number of man-hours a bridge costs is the number of bridges the builders cross while walking from the nearest forest to the island they are building to, counting the bridge being built. Builders can walk between two islands only if a bridge between them is already built. A forest therefore works as a starting point only after it is connected to the base camp.

The king has already checked that at least one way to connect all islands exists.

Consider this example. A green tile is a forest, gray is an island without a forest, and blue is water.

One optimal solution starts by building these bridges from the base camp.

That costs $1 + 2 + 1 + 2 + 3 + 4 = 13$.

The forest at row 3, column 3 is now connected to the base camp, so bridges can be built from there. The rest of the islands are connected by bridges built from that forest.

That costs $2 + 1 + 2 + 1 + 2 + 3 = 11$. The total is 24, and no plan costs less.

The first line contains an integer $T$, the number of test cases. $T$ test cases follow. The first line of each test case contains the number of rows $N$ and the number of columns $M$, separated by a space. The next $N$ lines contain exactly $M$ characters each. A 'T' is an island with a forest, a '#' is an island without a forest, and a '.' is water.

Limits

• $1 \le T \le 50$
• $2 \le N \le 30$
• $2 \le M \le 30$
• The top left cell is always a 'T'.
• Connecting all islands with bridges is possible.
• The grid holds at most 2 forests, counting the base camp.

For each test case, print one line of the form "Case #X: Y", where $X$ is the 1-based case number and $Y$ is the smallest number of man-hours needed to connect all islands.