Three Computers#13079

Three Computers

3 seconds
256 megabytes

A team of three students is participating in an unusual programming olympiad. Each team member has their own computer, so the team can work on three problems simultaneously.

The olympiad has problems. Problem can be solved only if one participant works on it without interruption from minute l_i to minute r_i inclusive. During one minute, a participant can work on only one problem, and a problem cannot be split between several participants. For example, one participant can solve problems that need minutes – and –, but not problems that need minutes – and –, because both need minute .

For solving problem , the team receives w_i points. Find the greatest total number of points the team can get.

Input

The first line contains a single integer (1 \le t \le 2 \cdot 10^5) — the number of test cases.

The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the number of problems.

Each of the next lines contains three integers l_i, r_i and w_i (1 \le l_i \le r_i \le 10^9, 1 \le w_i \le 10^9) — the first and last minute of problem and the number of points for it.

It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, print on a separate line a single integer — the greatest total number of points.

Examples

Example 1

Loading
Loading

Note

In the first test case, all four problems need minutes and , so at most three of them can be solved. It is most profitable to give up the problem worth points, and get 3 + 4 + 5 = 12 points.

In the second test case, the first four problems need minute , so one of them has to be given up. It is most profitable to give up the third problem. The other four problems can be solved: the first participant solves problems (minutes –) and (minutes –), the second solves problem , and the third solves problem . In total, 10 + 1 + 10 + 7 = 28 points.

In the third test case, the only problem can be solved.