## OPTSUB - Optimal Connected Subset

no tags

• A point P(x,y) is called an integer point if and only if both x and y are integers.
• W is the set which contains all the integer points on the plane.
• Two integer point P(x,y) and Q(x',y') are called adjacent if and only if |x-x'|+|y-y'|=1.
• S is a set of integer points if and only if S is a limited subset of W.
• If S is a set of integer points, R and T belong to S,and there exist a limited integer point sequence Q0(=R),Q1,Q2,...,Qk,Qk+1(=T) which satisfies that
• Qi!=Qj iff i!=j
• Qi and Qi+1 are adjacent, for each 0<=i<=k.
• Qi belongs to S, for each 0<=i<=k+1.
we call R and T are connected and the sequence Qi(0<=i<=k) is a path that connect R and T.
• If S is a set of integer points, X and Y are some integer points that belong to S, there exists one and only one path connected X and Y, then S is called an optimal set.

Given an optimal set V, your task is to find an optimal set B, satisfying that B is a subset of V and the sum of the weights of each integer point is maximum.

### Input

The very first line of the input contains a single integer T, the number of test cases. T blocks follow.

For each test case, the first line contains a single integer N=|V|(N<=1000). N lines follow, each contains 3 integers, the X-coordinate, the Y-coordinate and the weight(the absolute value of the weight<=100) of the ith integer point, separated by single spaces.

### Output

T lines,each contains a single integer - the maximum sum of weights.

### Example

```Input:
1
5
0 0 -2
0 1 1
1 0 1
0 -1 1
-1 0 1

Output:
2
```