Một đội bóng sẽ đứng thành các hàng để chụp ảnh. Vị trí của mỗi cầu thủ được xác định bởi hai số nguyên \(x\) và \(y\), trong đó \(y\) là số thứ tự của hàng, và \(x\) là khoảng cách của cầu thủ đó tính từ mép trái của hàng. Các giá trị \(x\) đều khác nhau.

Để bức ảnh trở nên thú vị hơn, bạn muốn đảm bảo rằng những cầu thủ đứng gần nhau phải mặc áo màu khác nhau. Để thực hiện điều này, bạn đặt ra quy tắc sau:

Với mỗi cầu thủ \(P\):

• Cầu thủ gần nhất bên phải \(P\) trong cùng một hàng (nếu có) phải có màu áo khác.
• Cầu thủ gần nhất bên phải \(P\) ở hàng trước đó (nếu có) phải có màu áo khác.
• Cầu thủ gần nhất bên phải \(P\) ở hàng tiếp theo (nếu có) phải có màu áo khác.

Nói một cách chính xác hơn, nếu có hai cầu thủ ở vị trí \((x_1, y_1)\) và \((x_2, y_2)\), với \(x_1 < x_2\), thì hai cầu thủ đó phải có màu áo khác nhau nếu:

• \(y_1 - 1 \le y_2 \le y_1 + 1\), và
• không tồn tại \(x_3\) sao cho có một cầu thủ ở \((x_3, y_2)\) và \(x_1 < x_3 < x_2\).

Hãy tìm số lượng màu áo tối thiểu cần thiết để có thể thực hiện được điều này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\), là số lượng bộ dữ liệu. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên \(N\), số lượng cầu thủ, tiếp theo là \(N\) dòng có dạng:

x y

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất ra:

Case #X: c

Ràng buộc

• \(1 \le T \le 100\)
• \(1 \le x \le 1000\)
• Các giá trị \(x\) đều khác nhau.

Phân nhóm

• Small dataset: \(1 \le y \le 15, 1 \le N \le 100\).
• Large dataset: \(1 \le y \le 30, 1 \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ụ

3
3
10 10
8 15
12 7
5
1 1
2 1
3 1
4 1
5 1
3
1 1
2 2
3 1

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

Nguồn

Google Code Jam 2009, Vòng 3, bài Football Team.

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