Năm 2008 sẽ được biết đến là một năm của sự thay đổi và chuyển giao, sự khởi đầu của một kỷ nguyên mới: tất nhiên, chúng ta đang nói về định dạng mới của Google Code Jam. Sự ra đời của cuộc thi này đã tập hợp rất nhiều cuộc thi lập trình tuyệt vời trong một năm duy nhất đến nỗi mọi người bắt đầu gọi nó là Năm của Code Jam.

Sphinny, một thí sinh đầy nhiệt huyết, đang nhìn vào lịch trong năm của mình và phát hiện ra rằng có rất nhiều cuộc thi lập trình đã được lên lịch. Cô đã đánh dấu mỗi ngày trong năm trên lịch theo một trong ba cách:

• Trắng: Cô sẽ không tham gia cuộc thi vào ngày này. Có thể không có cuộc thi nào được lên lịch, hoặc cô có những việc quan trọng hơn phải làm (chắc chắn là có những điều tốt đẹp khác trong cuộc sống!).
• Xanh: Cô chắc chắn sẽ tham gia một cuộc thi vào ngày này.
• Dấu chấm hỏi: Có một cuộc thi được lên lịch, nhưng cô vẫn chưa quyết định có tham gia hay không.

Lưu ý: Để đơn giản hóa bài toán, chúng ta giả định rằng không có khái niệm vòng loại: bạn không cần phải tham gia một cuộc thi này để đủ điều kiện tham gia một cuộc thi khác.

Ở một thế giới hơi khác so với thế giới của chúng ta, lịch của Sphinny có một số đặc điểm cần lưu ý: Nó có \(N\) tháng, và mỗi tháng có đúng \(M\) ngày.

Hình ảnh dưới đây mô tả một tờ lịch với 5 tháng, mỗi tháng có 8 ngày, 15 ngày màu xanh và 5 dấu chấm hỏi.

Nhìn vào tờ lịch đẹp đẽ của mình, Sphinny quyết định rằng mỗi ngày có tối đa 4 hàng xóm trong năm: Ngày trước đó trong cùng một tháng, ngày tiếp theo trong cùng một tháng, cùng một ngày ở tháng trước và cùng một ngày ở tháng sau.

Sphinny muốn tối đa hóa sự hạnh phúc của mình từ các cuộc thi này, và cô ước tính mức độ ảnh hưởng của các cuộc thi đối với sự hạnh phúc của mình là tổng các giá trị của tất cả các ngày màu xanh. Đối với mỗi ngày màu xanh, giá trị được tính như sau:

• Giá trị ban đầu là 4.
• Với mỗi hàng xóm màu xanh mà ngày đó có, giá trị giảm đi 1.

Bạn có thể nghĩ rằng Sphinny thích các cuộc thi, nhưng việc tham gia vào hai ngày liên tiếp khiến cô hơi mệt mỏi. Và vì lý do thẩm mỹ, việc tham gia vào cùng một ngày trong hai tháng liên tiếp cũng không tuyệt vời cho lắm.

Sphinny muốn lập kế hoạch cho năm của mình ngay bây giờ, và quyết định cho mọi ngày có dấu chấm hỏi xem nó nên là màu trắng hay màu xanh. Mục tiêu của cô đơn giản là tối đa hóa giá trị hạnh phúc.

Hình ảnh sau đây cho thấy một giải pháp cho ví dụ trên. Bằng cách thay đổi hai dấu chấm hỏi thành các ngày màu xanh, và ba dấu chấm hỏi còn lại thành các ngày màu trắng, cô có thể đạt được giá trị hạnh phúc là 42.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test theo định dạng sau.
Dòng đầu tiên có dạng "\(N\) \(M\)", trong đó \(N\) và \(M\) là hai số cho biết số tháng và số ngày mỗi tháng.
\(N\) dòng tiếp theo mỗi dòng chứa một chuỗi có độ dài \(M\). Ký tự thứ \(j\) trong chuỗi thứ \(i\) là một trong các ký tự {'#', '.', '?'}, cho biết trạng thái của ngày thứ \(j\) trong tháng thứ \(i\). '#' biểu thị một ngày màu xanh, '.' biểu thị một ngày màu trắng, và '?' biểu thị một ngày có dấu chấm hỏi.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất ra một dòng theo định dạng:

Case #X: Y

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(1 \le M, N \le 15\).
• Large dataset (Test set 2): \(1 \le M, N \le 50\).

Đ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ụ

2
3 3
.?.
.?.
.#.
5 8
.#...##.
.##..?..
.###.#.#
??#..?..
###?#...

Case #1: 8
Case #2: 42

Nguồn

Google Code Jam 2008, Chung kết thế giới, bài The Year of Code Jam.

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