Có \(N\) người của một trường tiểu học — một giáo viên và \(N-1\) học sinh — đang tham gia một chuyến dã ngoại. Họ khám phá một đồng cỏ là lưới hai chiều vô hạn gồm các ô vuông đơn vị. Mỗi người hiện đứng trong một ô; nhiều người có thể cùng đứng trong một ô.

Khi đến giờ về, giáo viên và tất cả học sinh phải tập trung trong cùng một ô. Đó có thể là ô nào cũng được vì xe buýt có thể đón họ ở bất cứ đâu. Các học sinh đã được dạy một thuật toán giúp việc tập trung dễ dàng hơn:

• Giáo viên là người số \(1\), còn các học sinh được đánh số từ \(2\) đến \(N\).
• Một hành động của một người là đi tới một trong \(8\) ô có chung ít nhất một cạnh hoặc một góc với ô hiện tại, hoặc chọn đứng yên trong ô hiện tại.
• Khi tín hiệu kết thúc chuyến dã ngoại vang lên, giáo viên kiểm tra xem cả \(N\) người đã ở cùng một ô chưa. Nếu rồi thì không cần hành động thêm. Nếu chưa, giáo viên bắt đầu một lượt:
  1. Trước tiên, giáo viên thực hiện một hành động như mô tả trên. Giáo viên tự quyết định sẽ đi đâu, nếu có di chuyển.
  2. Sau đó từng học sinh thực hiện một hành động, bắt đầu từ học sinh \(2\) và lần lượt đến học sinh \(N\); học sinh thứ \(i\) chỉ hành động sau khi người thứ \(i-1\) đã hành động. Hành động của các em là tất định: học sinh thứ \(i\) phải chọn phương án làm nhỏ nhất khoảng cách giữa tâm ô của mình và tâm ô của người thứ \(i-1\). Lựa chọn này không bao giờ nhập nhằng; đúng một trong \(9\) phương án cho khoảng cách nhỏ nhất.
• Khi lượt kết thúc, giáo viên lại kiểm tra xem mọi người đã ở cùng một ô chưa. Nếu chưa, một lượt khác bắt đầu, và cứ tiếp tục như vậy cho đến khi tất cả ở cùng một ô.

Nếu giáo viên lựa chọn sao cho số lượt là ít nhất, số lượt đó bằng bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), là số người trong chuyến dã ngoại. Tiếp theo là \(N\) dòng; dòng thứ \(i\) trong số đó mô tả người thứ \(i\) và chứa hai số nguyên \(R_i\), \(C_i\), lần lượt là chỉ số hàng và cột của ô người đó đứng lúc đầu.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)) và y là số lượt nhỏ nhất có thể cần dùng như mô tả trên.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

Test Set 1 (Visible):

• \(2 \le N \le 10\).
• \(0 \le R_i \le 8\) với mọi \(i\).
• \(0 \le C_i \le 8\) với mọi \(i\).

Test Set 2 (Hidden):

• \(2 \le N \le 10^4\).
• \(0 \le R_i \le 10^9\) với mọi \(i\).
• \(0 \le C_i \le 10^9\) với mọi \(i\).

Đ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ụ

5
3
3 2
0 2
0 0
3
2 2
2 2
2 2
9
1 1
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
2
8 0
0 8
4
1 0
1 3
2 2
0 2

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

Nguồn

Google Code Jam 2018, Vòng 3, bài Field Trip.

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