题目描述

Satyam 得到 $n$ 个二维平面上的不同点。保证所有给定点 $(x_i, y_i)$ 满足 $0 \leq y_i \leq 1$。从中任选三个不同的点作为顶点，可以组成多少个不同的非退化直角三角形 $^{\ast}$？

如果存在某个点 $v$，使得 $v$ 是三角形 $a$ 的顶点但不是三角形 $b$ 的顶点，则称三角形 $a$ 和 $b$ 不同。

$^{\ast}$ 非退化直角三角形指面积大于零且有一个内角为 $90^\circ$ 的三角形。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$），表示点的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$0 \leq x_i \leq n$，$0 \leq y_i \leq 1$），表示 Satyam 可以选择的第 $i$ 个点。保证所有 $(x_i, y_i)$ 两两不同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示可以组成的不同非退化直角三角形的数量。

样例

3
5
1 0
1 1
3 0
5 0
2 1
3
0 0
1 0
3 0
9
1 0
2 0
3 0
4 0
5 0
2 1
7 1
8 1
9 1

4
0
8

样例说明

对于第一个测试用例，四个三角形如下图所示：

由 ChatGPT 4.1 翻译

来源

Codeforces 2009D，英文题名 Satyam and Counting。