D. Тренировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп тренер команд Берляндского ГУ по программированию. Он решил собрать тренировку для своих команд перед квалификационным этапом.

У Монокарпа есть $$$n$$$ задач, которые еще не решал ни один из его студентов. У $$$i$$$-й задачи есть тема $$$a_i$$$ (целое число от $$$1$$$ до $$$n$$$) и сложность $$$b_i$$$ (целое число от $$$1$$$ до $$$n$$$), причем все задачи попарно различны, то есть нет двух задач, у которых одинаковы и тема, и сложность.

Монокарп решил выбрать из $$$n$$$ задач ровно $$$3$$$ задачи для тренировки, при этом должно выполняться хотя бы одно из двух условий (возможно, оба):

  • темы всех трех выбранных задач различны;
  • сложности всех трех выбранных задач различны.

Перед вами стоит задача определить количество способов, которыми Монокарп может выбрать три задачи для тренировки.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество задач, которые есть у Монокарпа.

В $$$i$$$-й из следующих $$$n$$$ строк следуют по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — тема и сложность $$$i$$$-й задачи.

Гарантируется, что нет двух задач, у которых одинаковы и тема, и сложность.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите количество способов выбрать три задачи для тренировки, которые удовлетворяют описанным в условии требованиям.

Пример
Входные данные
2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1
Выходные данные
3
10
Примечание

В первом примере можно взять следующие наборы по три задачи:

  • задачи с номерами $$$1$$$, $$$2$$$, $$$4$$$;
  • задачи с номерами $$$1$$$, $$$3$$$, $$$4$$$;
  • задачи с номерами $$$2$$$, $$$3$$$, $$$4$$$.

Таким образом, количество способов равно трем.