Cheating 2

A university teaches a course called "The Art of Cheating". The exam has a reputation for being hard, so some students try to copy from the person next to them.

The exam is held in a rectangular classroom with $N$ rows and $M$ columns. The classroom is divided into unit squares of size $1 \times 1$, and one unit square is one seat.

The instructor makes the following assumption in order to stop cheating. Every student always copies the answer sheet of the student sitting to the left, to the right, on the upper-left diagonal, or on the upper-right diagonal. The seating must therefore be arranged so that no student can copy from another student.

Under this rule two students sitting directly above and below each other in the same column cannot copy from each other, so both may be seated. Two students in the same row who sit side by side, or two students one row apart who sit on a diagonal, always give one of them a copy of the other's answer sheet.

A few students who were angry about the seating rule broke some desks, so certain seats cannot be used.

Given the shape of the classroom, find the largest number of students that can be seated so that nobody can cheat.

The first line contains the number of test cases $C$. Each test case has two parts.

The first part is one line with the height $N$ and the width $M$ of the classroom. ($1 \le M \le 80$, $1 \le N \le 80$)

The second part is exactly $N$ lines, each made of $M$ characters. Each character is either . for a usable seat or the lowercase x for a seat that cannot be used.

For each test case print, on its own line, the largest number of students that can take the exam in that classroom.