박테리아 전술

Becca와 Terry는 친한 라이벌인 미생물학자이다. 연구가 지쳤을 때 둘은 함께 게임을 한다. 게임은 R행 C열의 단위 칸 행렬에서 진행된다. 처음에 각 칸은 비어 있거나 방사성 물질을 담고 있다.

각 차례에 행렬에 빈 칸이 하나도 없으면, 그 차례의 플레이어는 진다. 그렇지 않으면 플레이어는 빈 칸을 하나 골라 박테리아 군집을 놓는다. 군집은 H(가로)와 V(세로) 두 종류가 있다.

• H 군집은 놓인 칸을 차지하고, 바로 서쪽 칸(있다면)과 바로 동쪽 칸(있다면)으로 퍼지려 한다.
• V 군집은 놓인 칸을 차지하고, 바로 남쪽 칸(있다면)과 바로 북쪽 칸(있다면)으로 퍼지려 한다.

군집이 칸으로 퍼지려 할 때마다 다음과 같다.

• 칸에 방사성 물질이 있으면 군집이 돌연변이를 일으키고, 군집을 놓은 플레이어가 진다.
• 칸이 비어 있으면 군집이 그 칸을 차지하고, 그 칸에서 퍼지는 규칙이 다시 적용된다.
• 칸에 이미 박테리아가 있으면(종류와 관계없이) 군집은 그 칸으로 퍼지지 않는다.

돌연변이를 일으키는 수만 남은 플레이어는 결국 진다.

Becca가 먼저 둔다. 둘은 한쪽이 질 때까지 번갈아 둔다. 두 플레이어가 최선을 다하면 누가 이기는가? Becca가 이긴다면, 그녀가 고를 수 있는 서로 다른 이기는 첫 수는 몇 개인가? 두 첫 수는 사용하는 칸이 다르거나, 군집 종류가 다르거나, 둘 다 다를 때에만 서로 다르다.

첫 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스는 행 수 R과 열 수 C를 담은 한 줄로 시작한다. 이어서 각각 C개의 문자로 이루어진 줄이 R줄 주어진다. i번째 줄의 j번째 문자는 i행 j열의 칸을 나타낸다. 각 문자는 .(빈 칸) 또는 #(방사성 물질이 있는 칸)이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 정수이다. Becca가 이기지 못하면 y는 0이다. 이길 수 있다면 y는 그녀가 둘 수 있는 서로 다른 이기는 첫 수의 개수이다.

1 ≤ T ≤ 100.

1번 케이스에서 Becca는 남서쪽 빈 칸에 H 군집을 놓을 수 없고, 북동쪽 빈 칸에 V 군집을 놓을 수 없다. 각각 방사성 칸으로 퍼져 Becca가 지기 때문이다. 지지 않는 첫 수는 다음 두 가지뿐이다.

1. 북서쪽 또는 북동쪽 빈 칸에 H 군집을 놓는다. 군집은 그 두 칸 중 다른 칸으로도 퍼진다.
2. 북서쪽 또는 남서쪽 빈 칸에 V 군집을 놓는다. 군집은 그 두 칸 중 다른 칸으로도 퍼진다.

전략 1을 택하면 Terry는 남서쪽 빈 칸에 V 군집을 놓을 수 있다. 전략 2를 택하면 Terry는 북동쪽 빈 칸에 H 군집을 놓을 수 있다. 어느 쪽이든 Becca는 다음 차례에 둘 칸이 없어 지고, Terry가 이긴다.

2번 케이스에서는 Becca의 모든 첫 수가 돌연변이를 일으킨다.

3번 케이스에서는 Becca의 첫 수 12개 중 5개가 돌연변이를 일으키지만, 나머지 7개는 이긴다. 둘째 행의 어느 칸에든 H 군집을, 둘째 열의 어느 칸에든 V 군집을 놓을 수 있다. 어느 경우든 빈 칸은 각각 1칸 또는 2칸으로 이루어진 서로 떨어진 두 묶음으로 나뉜다. 각 묶음에서는 한 종류의 군집만 놓을 수 있고, 놓으면 그 묶음의 빈 칸이 모두 찬다. Terry가 어느 묶음을 채우든 Becca가 나머지 묶음을 채워 Terry에게 둘 칸이 남지 않는다.

4번 케이스에서는 Becca의 서로 다른 첫 수 2개가 모두 이긴다.

5번 케이스에서는 Becca가 둘 수 있는 첫 수가 없다.