Bạn là chủ một tòa nhà gồm các căn hộ xếp thành lưới \(R\times C\); mỗi căn hộ là một ô vuông đơn vị có bốn bức tường. Bạn muốn cho thuê \(N\) căn, mỗi căn đúng một người thuê, và để trống các căn còn lại.

Đáng tiếc, tất cả người thuê tiềm năng đều ồn ào. Mỗi khi hai căn hộ có người ở chung một bức tường (không chỉ chạm nhau ở góc), tòa nhà nhận thêm một điểm bất hạnh. Chẳng hạn, một tòa nhà \(2\times2\) có người ở mọi căn có bốn bức tường được hai người hàng xóm dùng chung, nên mức bất hạnh là 4.

Nếu bố trí tối ưu \(N\) người thuê, mức bất hạnh nhỏ nhất của tòa nhà là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test là một dòng gồm ba số nguyên cách nhau bởi dấu cách: \(R\), \(C\), và \(N\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là mức bất hạnh nhỏ nhất có thể của tòa nhà.

Ràng buộc

• \(1 \le T \le 1000\).
• \(0 \le N \le R\times C\).

Phân nhóm

• Test Set 1 (Nhỏ): \(1 \le R\times C \le 16\).
• Test Set 2 (Lớn): \(1 \le R\times C \le 10000\).

Đ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 6
4 1 2
3 3 8
5 2 0

    ???+ success "Output"

        ```sample
Case #1: 7
Case #2: 0
Case #3: 8
Case #4: 0

??? "Giải thích"

    Trong Case #1, mọi căn đều có người ở và cả bảy bức tường bên trong đều có người thuê ở hai phía.

    Trong Case #2, có nhiều cách đặt hai người sao cho họ không chung tường. Một cách được minh họa bên dưới.

    Trong Case #3, chiến lược tối ưu là đặt tám người thành một vòng, để trống căn hộ ở giữa.

    Sau đây là hình minh họa cho ba test mẫu đầu. Mỗi bức tường đỏ làm tăng mức bất hạnh thêm một điểm.

    https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_ec097aa9.png

Nguồn

Google Code Jam 2015, Vòng 1B, bài Noisy Neighbors.

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