Problem A: 网线布置

Problem A: 网线布置

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 85  Solved: 8
[Submit][Status][Web Board]

Description

在新格尔软件公司,有N台电脑,编号为1N。现在只有1号电脑接入了网络,如果想让所有的电脑都接入网络,每台电脑可以特殊作为交换机(数据经过交换机处理不需要花费时间),就需要再连接一些网线(你可以认为网线能够提供的带宽无限大)。

可以把办公室想象成一个二维平面,每台电脑就是其中的一个点,如果两台电脑之间需要连接网线,那么网线从长度为min(|x1-x2,| , |y1-y2|  )

因为某种原因,需要1号电脑向每台电脑传输数据。现在求出1号电脑到其他所有电脑的最小时延之和。

现在,办公室主任菜怒文接到了这个任务,他希望你能帮帮他们算出这个最小值。

Input

题目包含多组数据。

输入的第一行有一个整数T (1≤T≤10) 代表有T组数据。

对于每组数据分为多行:

第一行有一个整数N (其中1≤N≤50000)

然后第二行到第N+1行,包含两个整数x,y(-10^8≤x ,y≤10^8) ,描述第i台电脑的坐标。

Output

对于每组数据,输出的第一行为Case #x: ,其中x是数据编号(从1开始),

第二行一个整数,题目答案。

Sample Input

1
3
1 1 
2 2 
3 3

Sample Output

Case #1:
3

HINT

[Submit][Status]