Ryan đang chơi Kingdom Rush, một trò chơi phòng thủ tháp (tower defense) dành cho một người chơi được phát triển bởi Ironhide Game Studio. Trong Kingdom Rush, người chơi kiếm được sao bằng cách hoàn thành các màn chơi theo cách được mô tả dưới đây. Có nhiều sao hơn giúp người chơi mạnh mẽ hơn; vì vậy, mặc dù Ryan có thể không hoàn thành được màn 2 ngay lập tức, anh ấy có thể hoàn thành nó sau khi kiếm được sao từ màn 1.

Trò chơi Kingdom Rush thực tế không hoạt động hoàn toàn giống như bài toán này. Việc đã từng chơi trò chơi này hay chưa không quan trọng để giải quyết bài toán.

Trong phiên bản Kingdom Rush của bài toán này, khi người chơi hoàn thành một màn chơi, người đó sẽ nhận được xếp hạng 1 sao hoặc xếp hạng 2 sao. Xếp hạng đó có thể cho phép người chơi kiếm được sao như sau:

• Nếu người chơi chưa bao giờ hoàn thành màn đó trước đây và hoàn thành nó với xếp hạng 1 sao, người chơi đó kiếm được 1 sao.
• Nếu người chơi chưa bao giờ hoàn thành màn đó trước đây và hoàn thành nó với xếp hạng 2 sao, người chơi đó kiếm được 2 sao.
• Nếu người chơi trước đó chỉ mới hoàn thành màn đó với xếp hạng 1 sao và lần này hoàn thành nó với xếp hạng 2 sao, người chơi kiếm thêm được 1 sao nữa.

Ngoài ra, không có cách nào khác để người chơi kiếm thêm sao.

Ryan có thể không hoàn thành được mọi màn chơi ngay lập tức. Đối với mỗi màn, trước khi có thể hoàn thành nó với xếp hạng 1 sao, anh ấy cần phải kiếm được một số lượng sao nhất định; và anh ấy sẽ cần một số lượng sao lớn hơn hoặc bằng thế để hoàn thành màn đó với xếp hạng 2 sao.

Ví dụ, giả sử có hai màn chơi:

• Màn 1 yêu cầu 0 sao để hoàn thành với xếp hạng 1 sao, và 1 sao để hoàn thành với xếp hạng 2 sao.
• Màn 2 yêu cầu 0 sao để hoàn thành với xếp hạng 1 sao, và 2 sao để hoàn thành với xếp hạng 2 sao.

Đây là một chuỗi các sự kiện có thể xảy ra với Ryan:

1. Ryan bắt đầu với 0 sao. Anh ấy có thể chọn hoàn thành màn 1 hoặc màn 2 với xếp hạng 1 sao. Anh ấy chọn hoàn thành màn 1 với xếp hạng 1 sao. Bây giờ anh ấy có 1 sao.
2. Bây giờ Ryan có thể hoàn thành màn 2 với xếp hạng 1 sao, hoặc màn 1 với xếp hạng 2 sao. Anh ấy chọn hoàn thành màn 1 với xếp hạng 2 sao. Bây giờ anh ấy có 2 sao.
3. Bây giờ Ryan có thể hoàn thành màn 2 với xếp hạng 2 sao. Anh ấy thực hiện điều đó, và bây giờ anh ấy có 4 sao.
4. Bây giờ anh ấy đã xong, đã hoàn thành tất cả các màn với xếp hạng 2 sao và kiếm được 4 sao (2 sao mỗi màn). Anh ấy đã hoàn thành các màn chơi tổng cộng 3 lần: màn 1 hai lần, và màn 2 một lần.

Ryan rất giỏi các trò chơi phòng thủ tháp, nhưng anh ấy cần sự giúp đỡ để phá đảo Kingdom Rush nhanh nhất có thể. Nhiệm vụ của bạn là tính toán xem anh ấy cần hoàn thành các màn chơi bao nhiêu lần để đạt được xếp hạng 2 sao ở mọi màn.

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, T. T bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất N, cho biết có bao nhiêu màn chơi trong trò chơi. N dòng tiếp theo. Dòng thứ i chứa hai số nguyên \(a_i\) và \(b_i\): tương ứng là số sao cần thiết để đạt được xếp hạng một sao hoặc xếp hạng hai sao ở màn i.

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ần tối thiểu Ryan phải hoàn thành các màn chơi để đạt được xếp hạng 2 sao ở mọi màn. Nếu Ryan không thể đạt được xếp hạng 2 sao ở mọi màn, y thay vào đó phải là chuỗi "Too Bad" (không có dấu ngoặc kép, nhưng viết hoa chính xác như vậy). Điều này cho thấy Ryan quá kém cỏi để có thể hoàn thành toàn bộ trò chơi Kingdom Rush.

Ràng buộc

• 1 ≤ T ≤ 100.
• 0 ≤ \(a_i\) ≤ \(b_i\) ≤ 2001.

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): 1 ≤ N ≤ 10.
• Tập kiểm tra 2 (Hidden Verdict): 1 ≤ N ≤ 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ụ

4
2
0 1
0 2
3
2 2
0 0
4 4
1
1 1
5
0 5
0 1
1 1
4 7
5 6

Case #1: 3
Case #2: 3
Case #3: Too Bad
Case #4: 6

Kingdom Rush được tạo ra bởi Ironhide Game Studio. Ironhide Game Studio không xác nhận và không có liên quan đến Google Code Jam.

Nguồn

Google Code Jam 2012, Vòng 1A, bài Kingdom Rush.

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