Description

For every pair of triplets, T_a = (I_a, J_a, K_a) and T_b = (I_b, J_b, K_b), we define the difference value between T_a and T_b as follows:

D(T_a, T_b) = max {I_a − I_b, J_a − J_b, K_a − K_b} − min {I_a − I_b, J_a − J_b, K_a − K_b}

Now you are given

N

triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

Input

The input consists of several test cases.

Each test case begins with a line containing an integer N

, denotes the number of triplets. Assume that we number the triplets as

T₁

,

T₂

, ... ,

T_N

. Then, there are following

N

lines, each line contains three integers, giving the elements of each triplet.

A case with N

= 0 indicates the end of the input.

Output

For each case, output a line with the sum of difference values between every unordered pair of triplets.

2
1 2 3
3 2 1
3
1 3 2
4 0 7
2 2 9
0

4
20

Hint

Case 1:

D

(

T₁

,

T₂

)=4

Case 2: D

(

T₁

,

T₂

)+

D

(

T₁

,

T₃

)+

D

(

T₂

,

T₃

)=8+8+4=20

You can assume that N

, the number of triplets in each case, will not exceed 200,000 and the elements in triplets fit into [-10

⁶

,10

⁶

].

The size of the input will not exceed 5 MB.

Source

POJ Monthly--2007.07.08

, Yuan, Xinhao