Problem 1122. -- 田地管理

1122: 田地管理

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 27  Solved: 9
[Submit][Status][Web Board]

Description

在公元2018年4月20日的凌晨,张老师做了一个神奇的梦!在梦里,张老师变成了辛格尔王国的田地管理员!伟大的辛格尔国王,通过多年征战,为辛格尔王国赢得了N块土地,这些土地都使用矩形进行描述,相互之间还有重叠的情况。但是国王毫不在意这些,他只想要张老师告诉他,他的土地需要多长的城墙才能够将所有土地围起来,如果张老师在4月22日下午5点之前,没有办法计算出结果,就把张老师扔进济海喂鱼!张老师为了能够成功的活下来,他只好将这个任务交给智慧的你了!

Input

题目包含多组数据。
第一行一个整数T,表示有T组测试数据。(1 ≤ T3)
对于每组数据分为N+1行:
第一行有一个整数N,表示一共有N块田地;(N5000)
接下来N行,每行四个整数xleft,ydown,xright,ytop,分别表示田地的左下角和右上角坐标。
所有坐标都在[-100000, 100000]范围内。

Output

对于每组数据,第一行输出Case #x: (x编号从1开始)
对于每组数据,输出1行,表示围墙的长度。

Sample Input

1
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

Sample Output

Case #1:
228

HINT

Source

[Submit][Status]