18589번 - Radar Scanner 다국어

There are n rectangle radar scanners on the ground. Their sides are all parallel to the coordinate axes. Each scanner covers some grid squares on the ground. The i-th scanner covers all the squares (x, y) satisfying x_i,1 ≤ x ≤ x_i,2 and y_i,1 ≤ y ≤ y_i,2.

Today, the radar system is facing a critical low-power problem. You need to choose exactly three scanners such that there exists a square covered by all scanners.

Your task is to count how many tuples (i, j, k) you can choose so that 1 ≤ i < j < k ≤ n and there exists a square covered by all three scanners i, j, and k.

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

Each test case starts with a line containing an integer n (3 ≤ n ≤ 100 000), denoting 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.