Server Time: Wed Feb 26, 2020 1:47 pm
Welcome ( logout
F - Rectangle Union
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 64 MB

Given some axis parallel rectangles, you have to find the union of their area. For example, see the shaded regions in the picture. Each rectangle will be denoted by four integers. They are x1, y1, x2, y2 where (x1, y1) denotes the lower left corner and (x2, y2) denotes the upper right corner.

a.png

For the picture above, there are three rectangles. For the yellow rectangle the co-ordinates are (0, 2) and (3, 6). For the blue rectangle the co-ordinates are (1, 3) and (6, 7). For the green rectangle the co-ordinates are (2, 1) and (5, 4). So, the union area is (the shaded region) 31 square units.

Input

Input starts with an integer T (≤ 13), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 30000). Each of the next n lines will contain four integers x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 109, x1 < x2, y1 < y2) denoting a rectangle.

Output

For each case, print the case number and the union area.

Sample Input

Output for Sample Input

2

3

0 2 3 6

1 3 6 7

2 1 5 4

2

0 0 4 4

1 1 2 5

Case 1: 31

Case 2: 17

Notes

Dataset is huge, use faster I/O methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan