Buổi tập huấn

Huấn luyện viên của đội tuyển lập trình có $n$ bài tập mà chưa học sinh nào từng làm. Bài tập thứ $i$ thuộc chủ đề $a_i$ và có độ khó $b_i$ (cả hai đều là số nguyên từ $1$ đến $n$). Không có hai bài tập nào trùng nhau, tức là không tồn tại hai bài có cùng chủ đề và đồng thời cùng độ khó.

Huấn luyện viên muốn chọn đúng $3$ bài trong $n$ bài để tạo thành một đề luyện tập. Bộ ba được chọn phải thoả mãn ít nhất một trong hai điều kiện sau (có thể thoả mãn cả hai):

• chủ đề của cả ba bài đôi một khác nhau;
• độ khó của cả ba bài đôi một khác nhau.

Hãy đếm số cách chọn ba bài tập thoả mãn yêu cầu. Hai cách chọn được coi là khác nhau nếu tập ba bài tập của chúng khác nhau; thứ tự các bài trong một cách chọn không quan trọng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ là số bài tập.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ là chủ đề và độ khó của bài tập thứ $i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số cách chọn ba bài tập thoả mãn yêu cầu.

Ràng buộc

• $1\le t\le 50000$
• $3\le n\le 2·{10}^5$
• $1\le a_i,b_i\le n$
• Không có hai bài tập nào có cùng chủ đề và đồng thời cùng độ khó.
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ