代码派对

比特镇的算法竞赛选手们应邀来到了小Q家中参加盛大的"代码派对"。小Q计划在家中举行一场ACM赛制的联谊赛，$3$个人为一队进行比赛。

为了让比赛更加有趣，也为了让大家能多多了解他人，小Q在花园的地上画出了一个$1000\times 1000$的网格图，从上往下依次编号为第$1$行到第$1000$行，从左往右依次编号为第$1$列到第$1000$列。小Q让每一名选手选择一个网格图内平行坐标轴的子矩形$(x_1,y_1)-(x_2,y_2)$，表示以$(x_1,y_1)$和$(x_2,y_2)$为对顶点的矩形，包含所有满足$x\in [x_1,x_2]$且$y\in [y_1,y_2]$的格子。

小Q规定，$i,j,k(1\leq i<j<k\leq n)$三人组成一支三人队伍能参赛，当且仅当这三个人选择的子矩形包含至少一个公共格子。请写一个程序，帮助小Q统计有多少种三人组合组成的队伍可以参赛。

第一组样例如下图：

第二组样例如下图：

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含一个正整数$n(3\leq n\leq 100000)$，表示选手人数。

接下来$n$行，每行四个正整数$x_1,y_1,x_2,y_2(1\leq x_1\leq x_2\leq 1000,1\leq y_1\leq y_2\leq 1000)$，分别表示每个选手选择的矩形的顶点坐标。

对于每组数据，输出一行一个整数，即满足条件的三人组合数量。

2
3
3 1 3 1
1 1 2 3
2 1 3 2
5
1 1 4 5
2 1 3 2
2 2 3 3
4 5 4 5
1 2 2 4

0
4

"字节跳动杯"2018中国大学生程序设计竞赛-女生专场