Nhiệm vụ của bạn trong bài toán này là tìm số lượng đá ít nhất cần đặt trên một lưới hình chữ nhật kích thước \(N \times M\) (\(N\) đoạn thẳng nằm ngang và \(M\) đoạn thẳng nằm dọc) để bao quanh ít nhất \(K\) điểm giao cắt. Một điểm giao cắt được coi là bị bao quanh nếu một trong hai điều kiện sau là đúng:

1. Một viên đá được đặt tại điểm đó.
2. Bắt đầu từ điểm đó, chúng ta không thể tìm được một đường đi dọc theo các đường lưới để đến một điểm trống trên biên của lưới mà chỉ đi qua các điểm giao cắt trống.

Ví dụ, để bao quanh 8 điểm trên lưới \(4 \times 5\), chúng ta cần ít nhất 6 viên đá. Một trong nhiều cách đặt đá hợp lệ được hiển thị bên dưới. Các điểm bị bao quanh được đánh dấu bằng chữ "x".

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên: \(N\) \(M\) \(K\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng đá tối thiểu cần thiết.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N\).
• \(1 \le M\).
• \(1 \le K \le N \times M\).

Phân nhóm

• Small dataset: \(N \times M \le 20\).
• Large dataset: \(N \times M \le 1000\).

Đ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
4 5 8
3 5 11

Case #1: 6
Case #2: 8

Nguồn

Google Code Jam 2014, Vòng 1C, bài Enclosure.

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