Bạn đang trong quá trình viết bản tóm tắt kinh tế cuối năm cho tờ báo của mình và bạn đã quyết định muốn hiển thị một số biểu đồ để chứng minh các loại cổ phiếu khác nhau đã hoạt động như thế nào trong suốt năm qua. Bạn đã quyết định rằng bạn muốn hiển thị giá của \(n\) loại cổ phiếu khác nhau, tất cả tại cùng \(k\) thời điểm trong năm.

Một biểu đồ đơn giản về giá của một loại cổ phiếu sẽ vẽ các đường thẳng giữa các điểm \((0, \text{price}_0), (1, \text{price}_1), \dots, (k-1, \text{price}_{k-1})\), trong đó \(\text{price}_i\) là giá của cổ phiếu tại thời điểm thứ \(i\).

Để tiết kiệm không gian, bạn đã phát minh ra khái niệm biểu đồ lồng nhau. Một biểu đồ lồng nhau là sự kết hợp của một hoặc nhiều biểu đồ đơn giản và hiển thị giá của nhiều loại cổ phiếu (chỉ đơn giản là vẽ một đường cho mỗi loại). Để tránh nhầm lẫn giữa các cổ phiếu được hiển thị trong một biểu đồ, các đường trong một biểu đồ lồng nhau không được cắt nhau hoặc chạm nhau.

Cho danh sách giá của \(n\) loại cổ phiếu tại mỗi thời điểm trong \(k\) thời điểm, hãy xác định số lượng biểu đồ lồng nhau tối thiểu bạn cần để hiển thị tất cả giá của các loại cổ phiếu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào sẽ chứa một số nguyên duy nhất \(T\), số lượng bộ thử nghiệm. Sau đó sẽ là \(T\) bộ thử nghiệm trên các dòng khác nhau, mỗi bộ có dạng:

n k
price0,0 price0,1 ... price0,k-1
price1,0 price1,1 ... price1,k-1
...
pricen-1,0 pricen-1,1 ... pricen-1,k-1

Trong đó \(\text{price}_{i,j}\) là một số nguyên, giá của cổ phiếu thứ \(i\) tại thời điểm \(j\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, in ra một dòng duy nhất chứa "Case #X: Y", trong đó \(X\) là số thứ tự của bộ thử nghiệm (bắt đầu từ 1) và \(Y\) là số lượng biểu đồ lồng nhau tối thiểu cần thiết để hiển thị giá của tất cả các cổ phiếu.

Ràng buộc

• \(1 \le T \le 100\)
• \(2 \le k \le 25\)
• \(0 \le \text{price}_{i,j} \le 1000000\)

Phân nhóm

• Small Input: \(1 \le n \le 16\).
• Large Input: \(1 \le n \le 100\).

Đ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
3 4
1 2 3 4
2 3 4 6
6 5 4 3
3 3
5 5 5
4 4 6
4 5 4
5 2
1 1
2 2
5 4
4 4
4 1

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

Nguồn

Google Code Jam 2009, Vòng 2, bài Stock Charts.

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