Một trường trung học địa phương sắp tổ chức một kỳ thi cuối kỳ trong một phòng học lớn. Tuy nhiên, một số học sinh trong trường này luôn cố gắng nhìn bài của nhau trong suốt kỳ thi!

Phòng học có thể được coi là một hình chữ nhật gồm \(M\) hàng và \(N\) cột các ô vuông đơn vị, trong đó mỗi ô vuông đơn vị đại diện cho một chỗ ngồi.

Hiệu trưởng nhà trường quyết định đặt ra quy tắc sau để ngăn chặn việc gian lận:
Giả sử một học sinh có thể nhìn thấy bài làm của những người hàng xóm bên trái, bên phải, phía trên bên trái và phía trên bên phải của mình. Việc sắp xếp chỗ ngồi phải đảm bảo rằng không có bài làm của ai có thể bị bất kỳ học sinh nào khác nhìn thấy.

Như trong hình này, sẽ không phải là ý kiến hay nếu xếp bất kỳ ai vào các vị trí A, C, D hoặc E vì cậu bé ở hàng sau sẽ có thể nhìn thấy bài làm của họ. Tuy nhiên, nếu có một cô gái ngồi ở vị trí B, cậu ấy sẽ không thể nhìn thấy bài làm của cô ấy.

Một số chỗ ngồi trong lớp học bị hỏng, và chúng ta không thể xếp học sinh vào chỗ ngồi bị hỏng.

Hiệu trưởng yêu cầu bạn trả lời câu hỏi sau: Số lượng học sinh tối đa có thể xếp vào lớp học sao cho không ai có thể gian lận là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(C\). Tiếp theo là \(C\) bộ test. Mỗi bộ test gồm hai phần.

Phần thứ nhất là một dòng duy nhất chứa hai số nguyên \(M\) và \(N\): Chiều cao và chiều rộng của phòng học hình chữ nhật.

Phần thứ hai sẽ có chính xác \(M\) dòng, với đúng \(N\) ký tự trong mỗi dòng. Mỗi ký tự là '.' (chỗ ngồi không bị hỏng) hoặc 'x' (chỗ ngồi bị hỏng, chữ x thường).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(X\): \(Y\)", trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1, và \(Y\) là số lượng học sinh tối đa có thể tham gia kỳ thi trong phòng học.

Ràng buộc

• \(C = 20\)

Tập dữ liệu nhỏ (Test set 1 - Visible)

• \(1 \le M \le 10\)
• \(1 \le N \le 10\)

Tập dữ liệu lớn (Test set 2 - Hidden)

• \(1 \le M \le 80\)
• \(1 \le N \le 80\)

Phân nhóm

Đề bài không chia thành các phân nhóm riêng.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

Nguồn

Google Code Jam 2008, Vòng 3, bài No Cheating.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.