提示: 欢迎访问OurACM平台。
Problem 1817 Squares

Accept: 43    Submit: 101
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

You will be given a number of rectangles in the plane and asked to determine the area that they cover. The rectangles may overlap.

Input

The first line of input will contain a single integer T ≤ 10 giving the number of test cases to follow. Each test case begins with a line with a single integer n giving the number of rectangles that will follow. There will be at most 20. The next n lines will describe the n rectangles. Each of these will consist of four whitespace separated integers xmin ymin xmax ymax. These coordinates will will fit within a signed 32-bit integer.

Output

For each test case, you are to output the total area covered by the squares.

Sample Input

1 3 0 0 4 10 1 -1 4 1 -2 -2 -1 -1

Sample Output

44

Source

2008-2009 North-America North-East Preliminary

Submit  Back  Status  Discuss