컨닝 2

한 대학에서 "컨닝의 기술"이라는 과목을 가르친다. 이 과목의 시험은 까다롭기로 소문이 나 있어서, 일부 학생은 시험 도중에 옆 사람의 답안지를 베끼려 한다.

시험은 $N$행 $M$열 크기의 직사각형 교실에서 치른다. 교실은 $1 \times 1$ 크기의 단위 정사각형으로 나뉘어 있고, 단위 정사각형 하나가 자리 하나다.

담당 교수는 컨닝을 막으려고 다음 가정을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위, 이렇게 네 자리에 앉은 학생의 답안지를 항상 베낀다. 따라서 어떤 학생도 다른 학생의 답안지를 베낄 수 없도록 자리를 배치해야 한다.

이 규칙에서 같은 열의 바로 위아래에 앉은 두 학생은 서로 베낄 수 없으므로 함께 앉혀도 된다. 반면 같은 행에서 바로 옆에 앉거나 한 행 차이로 대각선에 앉으면 둘 중 한 명이 상대의 답안지를 베낀다.

자리 배치에 화가 난 학생 몇 명이 책상을 부숴 놓아서, 일부 자리에는 학생이 앉을 수 없다.

교실의 모양이 주어졌을 때, 아무도 컨닝을 할 수 없도록 배치하면 최대 몇 명을 앉힐 수 있는지 구하라.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다. 각 테스트 케이스는 두 부분으로 이루어진다.

첫 번째 부분에는 교실의 세로 길이 $N$과 가로 길이 $M$이 한 줄에 주어진다. ($1 \le M \le 80$, $1 \le N \le 80$)

두 번째 부분에는 정확히 $N$개의 줄이 주어지고, 각 줄은 $M$개의 문자로 이루어진다. 각 문자는 앉을 수 있는 자리를 뜻하는 . 또는 앉을 수 없는 자리를 뜻하는 소문자 x 중 하나다.

각 테스트 케이스마다 그 교실에서 시험을 볼 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.