Problem Description

FJ has two same house for rant. Now he has n (1 ≤ n ≤ 1000) piece of order, the orders are given in the form:

s t v

means that someone want to rant a hours from the day s to t paying v yuan totally (including the day s and t, 0 ≤ s ≤ t ≤ 400, 0 ≤ v ≤ 100,0000).

A hours can be only rant to one person, and FJ should either accept an order totally or reject it.

Input

The first line of input file is a single integer T - The number of test cases. For each test case, the first line is a single integer n then there n lines, each line gives an order.

Output

For each data set, print a single line containing an integer, the maximum total income for the data set.

3
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640

30
25500
38595