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