Bạn đang chơi một trò chơi bài, trong đó mỗi lá bài có ghi một số nguyên trên đó.

Để chơi trò chơi, bạn được đưa cho một số lá bài — gọi là xấp bài của bạn. Sau đó, bạn sắp xếp các lá bài trong xấp bài của mình thành các dãy liên tiếp (straights). Một dãy liên tiếp là một tập hợp các lá bài có giá trị liên tiếp nhau; ví dụ: bộ ba lá bài \(\{3, 4, 5\}\), hoặc bộ một lá bài \(\{7\}\). Sau đó, bạn sẽ nhận được số đô la bằng với độ dài của dãy liên tiếp ngắn nhất. Nếu bạn không có lá bài nào, bạn không thể tạo ra dãy liên tiếp nào, vì vậy bạn nhận được 0 đô la.

Bạn sẽ được cung cấp một loạt các trường hợp kiểm thử, mỗi trường hợp mô tả các lá bài bạn có trong xấp bài của mình. Hãy tìm số đô la tối đa bạn có thể nhận được cho mỗi trường hợp kiểm thử.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng trường hợp kiểm thử, \(T\).

Mỗi trường hợp kiểm thử gồm một dòng. Mỗi dòng chứa \(N\), số lượng lá bài trong xấp bài của bạn, theo sau là \(N\) số nguyên cho biết các số trên những lá bài đó. Các số này đều được phân tách bằng dấu cách.

Dữ liệu ra

Đối với mỗi trường hợp kiểm thử, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự trường hợp kiểm thử (bắt đầu từ 1) và y là số đô la tối đa bạn có thể nhận được.

Ràng buộc

• \(1 \le T \le 100\).
• Các số trên lá bài nằm trong khoảng từ \(1\) đến \(10000\).

Phân nhóm

• Small dataset (Test set 1): \(0 \le N \le 10\).
• Large dataset (Test set 2): \(0 \le N \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ụ

4
10 1 2 3 4 5 10 9 8 7 6
8 101 102 103 104 105 106 103 104
0
5 1 2 3 4 9

Case #1: 10
Case #2: 4
Case #3: 0
Case #4: 1

Nguồn

Google Code Jam 2011, Vòng 3, bài Dire Straights.

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