Một công ty tọa lạc trong hai tòa nhà rất cao. Mạng nội bộ của công ty kết nối hai tòa nhà bao gồm nhiều sợi dây cáp, mỗi sợi nối một cửa sổ ở tòa nhà thứ nhất với một cửa sổ ở tòa nhà thứ hai.

Bạn đang quan sát những tòa nhà này từ bên cạnh, sao cho một tòa nhà ở bên trái và một tòa nhà ở bên phải. Các cửa sổ trên tòa nhà bên trái được xem như các điểm trên bức tường bên phải của nó, và các cửa sổ trên tòa nhà bên phải được xem như các điểm trên bức tường bên trái của nó. Các sợi dây là các đoạn thẳng nối một cửa sổ ở tòa nhà bên trái với một cửa sổ ở tòa nhà bên phải.

Bạn nhận thấy rằng không có hai sợi dây nào dùng chung một điểm đầu mút (nói cách khác, có tối đa một sợi dây đi ra từ mỗi cửa sổ). Tuy nhiên, từ góc nhìn của bạn, một số sợi dây cắt nhau ở giữa chừng. Bạn cũng nhận thấy rằng tại mỗi giao điểm chỉ có đúng hai sợi dây gặp nhau.

Trong hình trên, các giao điểm là các hình tròn màu đen, trong khi các cửa sổ là các hình tròn màu trắng.

Có bao nhiêu giao điểm mà bạn nhìn thấy?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), biểu thị số lượng sợi dây bạn nhìn thấy.

\(N\) dòng tiếp theo, mỗi dòng mô tả một sợi dây bằng hai số nguyên \(A_i\) và \(B_i\). Chúng mô tả các cửa sổ mà sợi dây này kết nối: \(A_i\) là độ cao của cửa sổ trên tòa nhà bên trái, và \(B_i\) là độ cao của cửa sổ trên tòa nhà bên phải.

Dữ liệu ra

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

Ràng buộc

• \(1 \le T \le 15\).
• \(1 \le A_i \le 10^4\).
• \(1 \le B_i \le 10^4\).
• Trong mỗi bộ test, tất cả các \(A_i\) đều khác nhau.
• Trong mỗi bộ test, tất cả các \(B_i\) đều khác nhau.
• Không có ba sợi dây nào cắt nhau tại cùng một điểm.

Phân nhóm

• Tập kiểm thử 1 (Small - Visible): \(1 \le N \le 2\).
• Tập kiểm thử 2 (Large - Hidden): \(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ụ

2
3
1 10
5 5
7 7
2
1 1
2 2

Case #1: 2
Case #2: 0

Nguồn

Google Code Jam 2010, Vòng 1C, bài Rope Intranet.

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