As you might already know, Ada the Ladybug is a farmer. She has a garden with kohlrabi. Each kohlrabi has assigned a quality, which is a number (possibly negative, since the kohlrabi might be rotten).

Ada wants to gather some kohlrabi so she wants to pick a line such that the sum of kohlrabi on the line is maximal. Can you help her to find such line?

Input

The first line of input contains 1 ≤ T ≤ 100, the number of test-cases (anyway note that for biggest test-cases there will be only 1 test-case).

The first line of each test-case contains 0 < N ≤ 3000, the number of kohlrabi.

The next N lines contains three integers x, y, q: -10⁹ ≤ x, y ≤ 10⁹, -10⁴ ≤ q ≤ 10⁴, the coordinates of kohlrabi and its quality (note that no two kohlrabi will grow on same coordinates).

Output

For each test-case, print the best achievable sum of qualities of kohlrabies on a single line.

Example Input

5
4
0 0 1
1 1 1
2 2 1
3 3 1
5
0 0 -10
1 0 2
0 1 3
-1 0 2
0 -1 3
3
0 0 -1
1 1 -2
1 3 -5
2
0 0 666
1 7 -666
5
0 0 1
99999999 0 6
0 99999999 5
-99999999 0 6
0 -99999999 5

Example Output

4
5
0
666
13

Example Input 2

1
7
10 8 -2
9 4 -1
-3 -5 -5
7 5 1
-3 2 -6
5 10 -4
9 7 10

Example Output 2

10

Example Input 3

1
4
-6 0 9
7 4 7
7 -6 -10
-6 7 10

Example Output 3

19

Example Input 4

1
6
-10 -1 -10
8 3 4
0 9 -2
4 -6 1
6 0 10
-6 1 -10

Example Output 4

14