삼국 통일

대륙 하나가 세 나라로 나뉘어 있다. 지도는 $R$행 $C$열 격자이고, 각 칸은 바다를 뜻하는 '.' 또는 땅을 뜻하는 'X'다. 상하좌우로 맞닿은 땅은 같은 나라에 속하며, 지도에는 나라가 정확히 세 개 있다.

바다 칸을 골라 땅으로 메울 수 있다. 세 나라가 모두 하나로 이어지도록 메워야 하는 바다 칸의 최소 개수를 구하라.

아래 그림은 $R = 6$, $C = 14$인 지도다. 왼쪽은 처음 지도, 가운데는 각 땅 칸이 속한 나라의 번호, 오른쪽은 바다 칸 두 개(x로 표시)를 메워 세 나라를 하나로 이은 결과다.

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

첫 줄에 지도의 개수 $Q$가 주어진다. ($1 \le Q \le 15$)

각 지도는 다음 형식으로 주어진다. 첫 줄에 $R$과 $C$가 공백으로 구분되어 주어진다. ($1 \le R, C \le 50$) 이어지는 $R$개의 줄에는 길이가 $C$인 문자열이 주어지며, '.'은 바다, 'X'는 땅이다.

모든 지도에는 나라가 정확히 세 개 있다.

지도마다 한 줄에, 세 나라를 모두 잇기 위해 메워야 하는 바다 칸의 최소 개수를 출력한다.