Slides

Time Limit: 3000 ms Memory Limit: 32768 KiB

Problem Description

There are N slides lying on the table. Each of them is transparent and formed as a rectangle. In a traditional problem, one may have to calculate the intersecting area of these N slides. The definition of intersection area is such area which belongs to all of the slides.

But this time I want to take out some one of the N slides, so that the intersecting area of the left N-1 slides should be maximal. Tell me the maximum answer.

Input

The first line of the input contains a single integer T, the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer N (1 <= N <= 100000), the number of rectangles. Followed by N lines, each line contains four integers x1, y1, x2, y2 (-10000 <= x1 < x2 <= 10000, -10000 <= y1 < y2 <= 10000), pair (x1, y1) gives out the bottom-left corner and pair (x2, y2) gives out the top-right corner of the rectangle.

Output

There should be one line per test case containing the maximum intersecting area of corresponding N-1 slides.

Sample Input

2
2
0 0 2 2
1 1 2 2
3
0 0 2 2
1 0 3 2
1 1 3 3

Sample Output

4
2

Hint

hdoj2478 有链接提示的题目请先去链接处提交程序,AC后提交到SDUTOJ中,以便查询存档。

Source

四川回锅肉——2008成都现场赛题目