| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 29 | 22 | 21 | 77.778% |
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 xi,1 ≤ x ≤ xi,2 and yi,1 ≤ y ≤ yi,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, xi,1, yi,1, xi,2, and yi,2 (1 ≤ xi,1 ≤ xi,2 ≤ 1000, 1 ≤ yi,1 ≤ yi,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.
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