Bạn có một bộ đặc biệt gồm \(N\) xúc xắc sáu mặt; trên sáu mặt của mỗi con là sáu số nguyên dương khác nhau. Các xúc xắc khác nhau có thể được đánh số khác nhau.

Bạn muốn xếp một số hoặc toàn bộ xúc xắc thành một hàng sao cho các mặt trên tạo thành một dãy thẳng, tức là hiển thị các số nguyên liên tiếp. Với mỗi xúc xắc, bạn được chọn mặt nào nằm trên.

Dãy thẳng dài nhất có thể tạo theo cách này dài bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa \(N\), số xúc xắc. Tiếp theo là \(N\) dòng, mỗi dòng gồm sáu số nguyên dương \(D_{ij}\); số thứ \(j\) trên dòng thứ \(i\) là giá trị ở mặt thứ \(j\) của xúc xắc thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ 1, và y là độ dài dãy thẳng dài nhất.

Ràng buộc

• \(1\le T\le100\).
• \(1\le D_{ij}\le10^6\) với mọi \(i,j\).

Phân nhóm

Test Set 1 (Small, hiển thị)

\(1\le N\le100\).

Test Set 2 (Large, ẩn)

• \(1\le N\le50000\).
• Tổng \(N\) trên mọi bộ test không quá 200000.

Đ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
4
4 8 15 16 23 42
8 6 7 5 30 9
1 2 3 4 55 6
2 10 18 36 54 86
2
1 2 3 4 5 6
60 50 40 30 20 10
3
1 2 3 4 5 6
1 2 3 4 5 6
1 4 2 6 5 3

Case #1: 4
Case #2: 1
Case #3: 3

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Dice Straight.

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