Description

Snow Wolf lives in a 3-D city. He wants to open a fast-food restaurant. And he wants to find a place to locate his restaurant where he can get the smallest total distance to all the people lived in the city. It's such a special city that one can only go in the three axes directions (And the distance is also calculated that way). For example if there are 3 persons lived in the city, and their locations are (1, 2, 3), (2, 3, 4), (3, 4, 5), his restaurant can locate at (2, 3, 4) to get the smallest total distance T = (|2 - 1| + |3 - 2| + |4 - 3|) + (|2 - 2| + |3 - 3| + |4 - 4|) + (|2 - 3| + |3 - 4| + |4 - 5|). Given the location of the people in the city, your task is to calculate the smallest total distance.

Input

The input contains multiply test cases. For each test case, the first line of the input is a single integer n (1 < n < 10000), indicating the number of people lived in the city. The following n lines each contains three integers xi, yi, zi .(-2^31 <= xi, yi, zi <= 2^31-1), indicating the locations of the people.

Output

For each test case, output the smallest total distance in a single line.

Sample Input

4
1 2 3
4 5 6
7 8 9
10 11 12
2
1 5 1
3 7 9

Sample Output

36
12

Hint

For large scale input, please use "scanf" to avoid Time Limit Exceeded. There will be no 64bit integers in the problem input file.

Source

Littlelotus