← 返回题目列表

Codeforces · 1598/D

D. 培训课程

中文机器翻译题面 查看原题

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$$$。

因此,路数等于三。