spoj#OPTSUB. Optimal Connected Subset

Optimal Connected Subset

  • 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

</p>