给定二维平面上的 $n$ 个互异的整点,我们需要你从中选出恰好 $4$ 个互异的点形成与坐标轴平行的矩形,请你计算有多少种选取方式。
第一行包含一个正整数 $T$ ,表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据:
第一行包含一个整数 $n$ ,表示平面上整点的数量。
接下来 $n$ 行,每行包含两个整数 $x$ 和 $y$ ,表示 $(x, y)$ 处有一个点。
保证所有的点坐标互不相同,输入数据不超过 30 MB
。
$1 \leq T \leq 20, 1 \leq n \leq 10^5, -10^9 \leq x, y \leq 10^9$
对于每组数据输出一行,包含一个整数,表示选取方式的数量。
注意:$\displaystyle{10^5 \choose 4} \leq 2^{63} - 1$
1
6
0 0
0 1
1 1
1 0
0 2
1 2
3
对于第一组数据,3
个矩形分别为 $[0, 1] \times [0, 1],$ $[0, 1] \times [0, 2],$ $[0, 1] \times [1, 2]$ 。