Uniting the Three Kingdoms

A continent is split into three countries. The map is a grid with $R$ rows and $C$ columns, and every cell is either sea, written '.', or land, written 'X'. Land cells that touch up, down, left, or right belong to the same country, and a map holds exactly three countries.

You may fill sea cells with land. Find the smallest number of sea cells you have to fill so that the three countries become one connected stretch of land.

The picture below shows a map with $R = 6$ and $C = 14$. The left panel is the original map, the middle panel labels each land cell with the number of its country, and the right panel fills two sea cells, marked x, so that the three countries connect.

XXX...........  111...........  111...........
X.X.XXXX......  1.1.2222......  1.1.2222......
XXX.X....XXXXX  111.2....33333  111.2....33333
X.X.X....X.X.X  1.1.2....3.3.3  1.1x2....3.3.3
....XXXX.X.X.X  ....2222.3.3.3  ....2222x3.3.3
.........X.X.X  .........3.3.3  .........3.3.3

The first line holds the number of maps $Q$ ($1 \le Q \le 15$).

Each map is given in this format. The first line holds $R$ and $C$ separated by a space ($1 \le R, C \le 50$). The next $R$ lines each hold a string of length $C$, where '.' is sea and 'X' is land.

Every map holds exactly three countries.

For each map, print on one line the smallest number of sea cells you have to fill so that the three countries connect.