Monocarp 是 Berland 州立大学编程队的教练。他决定为他的团队的培训课程编写一个问题集。
Monocarp 有 $$$n$$$ 问题,他的学生还没有见过。第 $$$i$$$ 问题有一个主题 $$$a_i$$$(从 $$$1$$$ 到 $$$n$$$ 的整数)和难度 $$$b_i$$$(从 $$$1$$$ 到 $$$n$$$ 的整数)。所有的问题都是不同的,也就是说,不存在两个任务同时具有相同的主题和难度。
Monocarp 决定从 $$$n$$$ 问题中准确选择 $$$3$$$ 问题作为问题集。这些问题应至少满足两个条件之一(可能同时满足两个条件):
- 所有三个选定问题的主题都不同;
- 三个选定问题的难度都不同。
您的任务是确定为问题集选择三个问题的方法数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — Monocarp 存在的问题数。
在接下来的 $$$n$$$ 行的第 $$$i$$$ 行中,有两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 第 $$$i$$$ 问题的主题和难度。
保证不存在两道题目同时相同、难度相同的问题。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印选择满足语句中描述的任一要求的三个训练问题的方法数。
示例
输入 #1
2 4 2 4 3 4 2 1 1 3 5 1 5 2 4 3 3 4 2 5 1
输出 #1
3 10
注意
在第一个示例中,您可以解决以下三组问题:
- 问题$$$1$$$、$$$2$$$、$$$4$$$;
- 问题$$$1$$$、$$$3$$$、$$$4$$$;
- 问题$$$2$$$、$$$3$$$、$$$4$$$。
因此,路数等于三。