부정행위 금지

한 지역 고등학교가 큰 교실에서 기말고사를 치르려고 한다. 하지만 이 학교의 일부 학생들은 시험 중에 항상 서로의 답안지를 보려고 한다!

교실은 단위 정사각형이 M행 N열로 배치된 직사각형으로 볼 수 있으며, 각 단위 정사각형은 좌석 하나를 나타낸다.

교장은 부정행위를 방지하기 위해 다음 규칙을 정했다: 한 학생이 자신의 왼쪽, 오른쪽, 왼쪽 위, 오른쪽 위에 있는 이웃 학생들의 답안지를 볼 수 있다고 가정한다. 좌석 배치는 어느 누구의 답안지도 다른 학생에게 보이지 않도록 보장해야 한다.

이 그림에서처럼 뒷줄의 남학생이 A, C, D, E에 앉은 사람의 답안지를 볼 수 있으므로, 그 좌석들에 누군가를 앉히는 것은 좋은 생각이 아니다. 하지만 B에 여학생이 앉아 있다면 그는 그 여학생의 답안지를 볼 수 없다.

교실의 일부 좌석은 고장 나 있으며, 고장 난 좌석에는 학생을 앉힐 수 없다.

교장은 여러분에게 다음 질문에 답해 달라고 요청했다. 아무도 부정행위를 할 수 없도록 교실에 배치할 수 있는 학생 수의 최댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. C = 20

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ M ≤ 10 1 ≤ N ≤ 10

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ M ≤ 80 1 ≤ N ≤ 80

입력의 첫 번째 줄에는 테스트 케이스의 수 C가 주어진다. 이어서 C개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 부분으로 구성된다.

첫 번째 부분은 두 정수 M과 N이 주어지는 한 줄이다. 이들은 직사각형 교실의 높이와 너비를 나타낸다.

두 번째 부분은 정확히 M개의 줄로 이루어지며, 각 줄에는 정확히 N개의 문자가 있다. 각 문자는 '.'(좌석이 고장 나지 않음) 또는 'x'(좌석이 고장 났으며, 소문자 x) 중 하나이다.

각 테스트 케이스마다 "Case #X: Y"을 포함하는 한 줄을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 교실에서 시험을 치를 수 있는 학생 수의 가능한 최댓값이다.