Server Time: Mon Oct 26, 2020 7:32 am
Welcome ( logout
D - Tunnels
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Fourth Great and Bountiful Human Empire is developing a trans-conduit tunnel network connecting all its planets. The Empire consists of N planets, represented as points in the 3D space. The cost of forming a trans-conduit tunnel between planets A and B is:

TunnelCost[A,B] = min{ |xA - xB|, |yA - yB|, |zA - zB| }

where (xA, yA, zA) are 3D coordinates of planet A, and (xB, yB, zB) are coordinates of planet B. The Empire needs to build exactly N - 1 tunnels in order to fully connect all planets, either by direct links or by chain of links.

You need to come up with the lowest possible cost of successfully completing this project.

Input

Input starts with an integer T (≤ 8), denoting the number of test cases. Each case starts with a blank line.

The first line of input contains one integer N (1 ≤ N ≤ 50000), number of planets. Next N lines contain exactly 3 integers each. All integers are between -109 and 109 inclusive. Each line contains the x, y, and z co-ordinate of one planet (in order). No two planets will occupy the exact same point in space.

Output

Output should contain the minimal cost of forming the network of tunnels.

Sample Input

Output for Sample Input

3

 

2

1 5 10

7 8 2

 

3

-1 -1 -1

5 5 5

10 10 10

 

5

11 -15 -15

14 -5 -15

-1 -1 -5

10 -4 -1

19 -4 19

3

11

4

 


Problem Source: COCI 2009/2010, Contest 7
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan