Radar Scanner

There are n rectangular radar scanners on the plane. Their sides are all parallel to the coordinate axes. Each scanner covers some grid squares on the plane. The i-th scanner covers all squares $(x, y)$ satisfying $x_{i,1} \le x \le x_{i,2}$ and $y_{i,1} \le y \le y_{i,2}$.

Today, the radar system is facing a critical low-power problem. To reduce coverage, you must choose exactly three scanners, and there must be at least one square covered by all three chosen scanners.

Find the number of tuples $(i, j, k)$ such that $1 \le i < j < k \le n$ and there exists a square covered by all of scanners i, j, and k.

The first line of the input contains an integer T (1 ≤ T ≤ 10), the number of test cases.

Each test case starts with a line containing an integer n (3 ≤ n ≤ 100 000), the number of radar scanners.

Each of the next n lines contains four integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, and $y_{i,2}$ (1 ≤ $x_{i,1}$ ≤ $x_{i,2}$ ≤ 1000, 1 ≤ $y_{i,1}$ ≤ $y_{i,2}$ ≤ 1000), describing the i-th radar scanner.

For each test case, print a single line containing a single integer: the number of possible tuples.