Bạn sắp chơi một phiên bản đơn giản của trò "bắn tàu" với cậu em trai. Bàn chơi là lưới chữ nhật có \(R\) hàng và \(C\) cột. Khi bắt đầu, bạn nhắm mắt và giữ nguyên như vậy tới cuối trò chơi. Em trai lấy một con tàu chữ nhật kích thước \(1\times W\) và đặt nằm ngang ở đâu đó trên bàn. Tàu phải luôn nằm hoàn toàn trong bàn, mỗi ô của tàu chiếm đúng một ô lưới, và không bao giờ được xoay.

Mỗi lượt, bạn gọi tên một ô trên bàn; em trai cho biết đó là trúng (ô có một phần tàu) hay trượt. (Em trai không nói bạn đã trúng phần nào của tàu, chỉ nói ô được gọi có phần tàu trong đó.) Bạn có trí nhớ hoàn hảo và theo dõi được mọi thông tin đã nhận. Khi đã gọi tên tất cả ô mà tàu chiếm, trò chơi kết thúc (tàu chìm), và điểm của bạn là số lượt đã dùng. Mục tiêu là giảm điểm này.

Dù tàu lẽ ra không được di chuyển sau khi đặt, bạn biết cậu em nghịch ngợm định gian lận: cậu có thể đổi vị trí tàu bất cứ lúc nào, miễn tàu vẫn nằm ngang, hoàn toàn trong bàn, và vị trí mới phù hợp với toàn bộ thông tin đã đưa ra trước đó.

Ví dụ, với bàn \(1\times4\) và tàu \(1\times2\), ban đầu em có thể đặt tàu phủ hai cột ngoài cùng bên trái. Nếu lượt đầu bạn đoán hàng 1, cột 2, em có thể bí mật chuyển tàu sang hai cột ngoài cùng bên phải và nói \((1,2)\) là trượt. Nhưng nếu lượt kế tiếp bạn đoán \((1,3)\), em không thể vừa nói đó cũng là trượt vừa chuyển tàu về vị trí ban đầu, vì như vậy mâu thuẫn với câu trả lời trước về \((1,2)\).

Không chỉ bạn biết em trai sẽ gian lận, em trai cũng biết rằng bạn biết. Nếu cả hai đều chơi tối ưu (bạn giảm điểm, em tăng điểm), điểm thấp nhất mà bạn có thể bảo đảm đạt được bất kể em trai làm gì 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 có ba số nguyên \(R\), \(C\), \(W\): số hàng, số cột của bàn và chiều rộng tàu.

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à số lượt nhỏ nhất bạn có thể bảo đảm.

Ràng buộc

• \(1 \le W \le C\).

Phân nhóm

• Test Set 1 (Nhỏ): \(T=55\), \(R=1\), \(1 \le C \le 10\).
• Test Set 2 (Lớn): \(1 \le T \le 100\), \(1 \le R \le 20\), \(1 \le C \le 20\).

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

3
1 4 2
1 7 7
2 5 1

    ???+ success "Output"

        ```sample
Case #1: 3
Case #2: 7
Case #3: 10

??? "Giải thích"

    Trong Case #1, bàn có một hàng, bốn cột và tàu chiếm một hàng, hai cột. Một chiến lược tối ưu là bắt đầu bằng ô $(1,2)$.

    Nếu em trai nói trúng, ô còn lại của tàu phải là $(1,1)$ hoặc $(1,3)$, và bạn chỉ cần gọi cả hai. Nếu bạn tình cờ gọi đúng ô đang chứa phần còn lại, em trai sẽ chuyển tàu sao cho $(1,2)$ vẫn trúng nhưng lần đoán mới là trượt. Lưu ý em vẫn có thể chuyển tàu sau khi đã bị bắn trúng, miễn vị trí mới không mâu thuẫn với thông tin đã cho.

    Nếu em trai nói trượt, kịch bản phù hợp duy nhất còn lại là tàu ở $(1,3)$ và $(1,4)$; từ đó em không thể đổi vị trí nữa, và bạn chỉ cần gọi hai ô đó.

    Vì thế, bất kể em làm gì sau khi bạn gọi $(1,2)$, bạn đều kết thúc sau nhiều nhất hai lượt nữa, tổng cộng ba lượt.

    Hơn nữa, ba lượt là tối ưu vì không thể bảo đảm kết thúc trong hai lượt. Không mất tính tổng quát, xét một lượt đầu bất kỳ. Dù chọn ô nào, vẫn còn một đoạn $1\times2$ trống để em trai chuyển tàu tới và tuyên bố bạn trượt. Không thể đánh chìm con tàu chưa trúng lần nào chỉ với một lượt còn lại.

    Trong Case #2, tàu lấp kín bàn nên em trai chỉ có một vị trí đặt. Bạn chỉ cần gọi mọi ô.

    Trong Case #3, em trai luôn có thể chuyển tàu $1\times1$ tới một ô bạn chưa thử, nên bạn phải gọi cả 10 ô và chỉ trúng (đồng thời đánh chìm tàu) ở ô cuối cùng.

Nguồn

Google Code Jam 2015, Vòng 1C, bài Brattleship.

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