地面上有 $n$ 个矩形雷达扫描仪。它们的边都平行于坐标轴。每个扫描仪覆盖地面上的一些网格方块。第 $i$ 个扫描仪覆盖所有满足 $x_{i,1} \le x \le x_{i,2}$ 且 $y_{i,1} \le y \le y_{i,2}$ 的方块 $(x, y)$。

今天，雷达系统面临一个严重的低功耗问题。你需要恰好选择三个扫描仪，使得存在一个被这三个扫描仪共同覆盖的方块。

你的任务是计算有多少个三元组 $(i, j, k)$，满足 $1 \le i < j < k \le n$，且存在一个被扫描仪 $i$、$j$ 和 $k$ 共同覆盖的方块。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 100\,000$)，表示雷达扫描仪的数量。

接下来的 $n$ 行，每行包含四个整数 $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$ ($1 \le x_{i,1} \le x_{i,2} \le 1000$, $1 \le y_{i,1} \le y_{i,2} \le 1000$)，描述第 $i$ 个雷达扫描仪。

输出格式

对于每个测试用例，输出一行，包含一个整数：满足条件的三元组数量。

样例

输入 1

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

输出 1

0
4