박테리아 전술

Becca와 Terry는 선의의 경쟁 관계에 있는 미생물학자들이다. 연구에서 잠시 쉴 필요가 있을 때면 함께 게임을 즐긴다. 이 게임은 R개의 행과 C개의 열로 이루어진 단위 칸의 행렬에서 진행된다. 처음에 각 칸은 비어 있거나 방사성 물질을 포함한다.

각 플레이어의 차례에 행렬에 빈칸이 없으면 그 플레이어가 게임에서 패배한다. 그렇지 않으면 빈칸 하나를 골라 그곳에 박테리아 군체를 놓는다. 박테리아 군체에는 H("수평")와 V("수직")의 두 유형이 있다.

• H형 군체를 빈칸에 놓으면 그 칸을 차지하여 빈칸이 아니게 만들고, 바로 서쪽에 있는 칸(존재하는 경우)과 바로 동쪽에 있는 칸(존재하는 경우)으로도 퍼지려고 한다.

• V형 군체를 빈칸에 놓으면 그 칸을 차지하여 빈칸이 아니게 만들고, 바로 남쪽에 있는 칸(존재하는 경우)과 바로 북쪽에 있는 칸(존재하는 경우)으로도 퍼지려고 한다.

어느 유형이든 군체가 칸으로 퍼지려고 할 때마다 다음과 같이 처리한다.

• 그 칸에 방사성 물질이 있으면 군체가 돌연변이를 일으키고, 그 군체를 놓은 플레이어가 게임에서 패배한다.

• 그 칸이 비어 있으면 군체가 그 칸을 차지하여 빈칸이 아니게 만들고, 위의 규칙이 다시 발동한다. 즉, 군체가 더 멀리 퍼지려고 한다.

• 그 칸에 이미 어느 유형이든 박테리아가 있으면 군체는 그 칸으로 퍼지지 않는다.

플레이어가 할 수 있는 모든 수가 그 플레이어를 패배하게 만들 수도 있으며, 이 경우 그 플레이어에게는 패배할 운명밖에 없다는 점에 유의하라. 게임의 진행 방식에 관한 예시는 아래의 예제 케이스 설명을 참고하라.

Becca가 먼저 수를 두고, 그 뒤 두 플레이어는 한 명이 게임에서 패배할 때까지 번갈아 수를 둔다. 두 플레이어가 모두 최적으로 플레이한다면 누가 승리하는가? 그리고 Becca가 승리한다면, 서로 다른 이기는 첫 수는 몇 개인가? (두 첫 수가 서로 다른 칸이나 서로 다른 종류의 군체를 사용하거나, 또는 둘 다에 해당할 때, 그리고 그럴 때에만 두 첫 수는 서로 다르다.)

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100.

테스트 세트 1 (공개)

1 ≤ R ≤ 4. 1 ≤ C ≤ 4.

테스트 세트 2 (비공개)

1 ≤ R ≤ 15. 1 ≤ C ≤ 15.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 두 정수 R과 C를 포함하는 한 줄로 시작하며, 각각 행렬의 행 수와 열 수를 나타낸다. 그다음 각각 C개의 문자로 이루어진 R개의 행이 더 주어진다. 이 줄들 중 i번째 줄의 j번째 문자는 행렬의 i번째 행 j번째 열을 나타낸다. 각 문자는 .(빈칸) 또는 #(방사성 물질이 있는 칸)이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 정수이다. Becca가 승리하지 못하면 0이고, Becca가 승리한다면 위에서 설명한 대로 Becca가 둘 수 있는 서로 다른 이기는 첫 수의 개수이다.

예제 케이스 #1에서 Becca는 남서쪽 빈칸에 H형 군체를 놓거나 북동쪽 빈칸에 V형 군체를 놓을 수 없다. 그렇게 하면 군체가 방사성 칸으로 퍼져 Becca가 패배하기 때문이다. 즉시 패배하지 않는 가능한 전략은 두 가지뿐이다.

• 북서쪽 또는 북동쪽 빈칸에 H형 군체를 놓는다. 군체는 그 두 칸 중 나머지 칸으로도 퍼진다.

• 북서쪽 또는 남서쪽 빈칸에 V형 군체를 놓는다. 군체는 그 두 칸 중 나머지 칸으로도 퍼진다.

Becca가 전략 1을 선택하면 Terry는 남서쪽 빈칸에 V형 군체를 놓을 수 있다. Becca가 전략 2을 선택하면 Terry는 북동쪽 빈칸에 H형 군체를 놓을 수 있다. 어느 쪽이든 Becca의 다음 차례에는 선택할 빈칸이 없으므로 Becca가 패배하고 Terry가 승리한다.

예제 케이스 #2에서는 Becca가 어떤 첫 수를 두더라도 돌연변이가 일어난다.

예제 케이스 #3에서는 Becca가 둘 수 있는 첫 수 중 다섯 개가 돌연변이를 일으키지만, 나머지 일곱 개는 이기는 수이다. Becca는 두 번째 행의 어느 칸에든 H형 군체를 놓거나, 두 번째 열의 어느 칸에든 V형 군체를 놓을 수 있다. 어느 경우든 각각 1개 또는 2개의 칸으로 이루어진, 서로 연결되지 않은 두 집합을 남긴다. 각 집합에서는 한 유형의 군체만 놓을 수 있으며, 그 군체를 놓으면 해당 집합의 모든 빈칸을 차지한다. 따라서 Terry가 그 집합들 중 어느 것을 차지하든 Becca가 나머지를 차지할 수 있으므로 Terry에게 둘 수 있는 수가 남지 않는다.

예제 케이스 #4에서는 Becca가 둘 수 있는 서로 다른 두 첫 수가 모두 이기는 수이다.

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