It is well-known that we can uniquely represent any point P on the Cartesian coordinate system using an ordered pair (x, y). If both x and y are integers, then we shall call P an integer point, otherwise we shall call P a non-integer point. We shall denote all integer points on the plane using the set W.

Definition 1: For two points P₁(x₁, y₁), P₂(x₂, y₂), if |x₁ − x₂| + |y₁ − y₂| = 1, then P₁ and P₂ shall be considered neighbors, which is denoted as P₁ ~ P₂. Otherwise, P₁ and P₂ are considered non-neighboring.

Definition 2: The set S is a finite subset of W such that S = {P₁, P₂, …, P_n} (n ≥ 1), where P_i (1 ≤ i ≤ n) belongs in W. We shall call S a set of integer points.

Definition 3: Where S is a set of integer points, if the points R and T belong to S, and there exists a finite sequence Q₁, Q₂, …, Q_k satisfying the following:

1. Q_i belongs to S (1 ≤ i ≤ k);
2. Q₁ = R, Q_k = T;
3. Q_i ~ Q_i+1 (1 ≤ i ≤ k−1) — i.e. Q_i and Q_i+1 are neighbours; and
4. Q_i ≠ Q_j for any 1 ≤ i < j ≤ k

then we shall say that R and T are connected within set S, where the sequence Q₁, Q₂, …, Q_k shall be called a pathway connecting points R and T.

Definition 4: For a set of integer points V, if for any two of V's integer points there exists exactly one pathway connecting them, then V shall be known as a singular set of integer points.

Definition 5: For any integer point on the plane, we can assign it an integer score. Thus, we shall call the sum of the scores of all the points in a set of integer points its total score.

Given a singular set of integer points V, we would like to find the optimally connected subset B, where:

1. B is a subset of V;
2. any two integer points in B is connected within B; and
3. out of the set of integer points satisfying 1 and 2, B is the set where the total score is highest.

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). Within the following N lines, the i-th line (1 ≤ i ≤ N) contains three space-separated integers X_i, Y_i, and C_i (−10⁶ ≤ X_i, Y_i ≤ 10⁶; −100 ≤ C_i ≤ 100), representing the coordinates of the i-th point along with its score.

Output

T lines, each line should consist of one integer, the total score of the optimally connected subset.

Example

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

Output:
2