벌집

벌집은 육각기둥 모양의 셀이 모인 구조다. 각 셀은 인접한 셀을 여섯 개 가지며, 인접한 두 셀은 변을 하나 공유한다. 일부 변은 지나갈 수 있고, 나머지 변은 지나갈 수 없다.

Hamilton은 성실한 일벌이다. 그는 매일 벌집에서 인접한 셀 쌍을 연결하거나 연결을 끊는다. 며칠 뒤 그는 셀로 이루어진 작은 블록을 직접 설계할 기회를 얻는다. 이 블록은 바깥과 연결되어 있지 않으며, 아래 그림과 같이 $n$개의 행과 $m$개의 열로 셀이 배치되어 있다.

두 셀의 연결을 끊으려면 일부 변을 지나갈 수 없는 변으로 바꿔야 할 수도 있다. 블록 안의 지정된 두 셀이 서로 떨어지도록 바꿔야 하는 변의 최소 개수를 구하려 한다. 블록에 있는 특수 셀의 모든 쌍에 대해 이 최소 개수를 구한다. 출력이 너무 커지지 않도록 이 최소 개수들의 합을 보고한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 두 정수 $n$과 $m$이 주어진다.

이어서 $(4n+3)$줄에 블록이 그려져 있다. 각 줄은 최대 $(6m+3)$글자다. 홀수 번째 줄에는 + 기호로 표시된 격자점과 가로 변이 있고, 짝수 번째 줄에는 대각선 변이 있다.

셀 하나는 꼭짓점 6개와 변 6개로 이루어진다. 각 변을 나타내는 글자는 두 꼭짓점 사이의 정가운데에 놓인다.

• 위쪽 또는 아래쪽 경계는 지나갈 수 없는 변이면 하이픈 세 개(---)로, 지나갈 수 있는 변이면 공백 세 개로 표시된다.
• 대각선 변은 지나갈 수 있으면 공백 한 칸으로 표시된다. 지나갈 수 없으면 방향에 따라 / 또는 \ 한 글자로 표시된다.

특수 셀은 중심에 별표(*)가 있다. 그 밖의 모든 글자는 공백이며, 줄 끝에 공백은 없다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 그 테스트 케이스의 답이다.

• $1 \le T \le 100$
• $2 \le n, m \le 100$
• 특수하지 않은 셀의 변은 모두 지나갈 수 없다.
• 모든 테스트 케이스에 걸친 특수 셀의 총수는 3000 이하다.