You are the mayor of a very old city. The ciry has n major tourist attractions. You are given the locations (x, y, z) for each of these tourist attractions.

To boost the tourism in your city, you can plan to create new roads that connect the tourist attractions.

To create a bidirectional road between tourist attraction A (located at (x1, y1, z1)) and B (located at (x2, y2, z2)), you need to spend min(|x1 - x2|, |y1 - y2|, |z1 - z2|) dollars. Here |x1 - x2| refers to the absolute value of x1 - x2, and min(x, y, z) refers to the minimum value out of x, y and z.

You need to create a network of roads such that it is possible to travel between any pair of tourist attractions using some sequence of roads. What is the minimum amount of dollars you need to spend in order to accomplish this task?

Sample Input

n = 3

locations = 
[[1, 5, 7],
[2, 9, 4],
[1, 3, 9]
]

Expected Output

1

Explanation

We can create 2 roads -

1. Road connecting attraction 1 (at (1, 5, 7)) and attraction 3 (at (1, 3, 9)). The cost of creating this road is min ( | 1 - 1 | , | 5 - 3 | , | 7 - 9 |) = min ( 0 , 2 , 2 ) = 0.

2. Road connecting attraction 1 (at (1, 5, 7)) and attraction 2 (at (2, 9, 4)). The cost of creating this road is min ( | 1 - 2 | , | 5 - 9 | , | 7 - 4 |) = min ( 1 , 4 , 3 ) = 1.

Creating these two roads enables us to travel between any pair of tourist attractions.
The total cost of creating these roads is 1 dollar.

• [execution time limit] 3 seconds (java)
• [input]integer n
  The number of mahor tourist attractions in the city
  2 <= n <= 100000
• [input] array.array.integer locations
  A matrix consisting of n rows. Each row has 3 integers = Xi, Yi, Zi - which describe the location of i th attraction.
  All coordinates are integers, and
  -100000 <= Xi, Yi, Zi <= 100000 for all i.
• [output] integer64