시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 4 4 100.000%

문제

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.

예제 입력 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