Phoebe and Honey were watching the ice skating event at the Winter Olympics when they became fascinated by the shapes carved into the rink. Some skaters swept across the ice in smooth arcs, others crossed paths at just the right moment, and together their movements seemed to form a strange but beautiful Olympic pattern.

After the event, Phoebe tried to recreate the choreography on paper. She drew each skating path as a closed interval on a line and assigned it a beauty value based on how graceful the movement looked. Honey, impressed by the drawing but unwilling to let anything remain purely artistic, decided to turn the pattern into a challenge.

You are given ~n~ closed intervals. The ~i~-th interval is ~[l_i, r_i]~ and has a given beauty ~s_i~.

An ordered 5-tuple of intervals ~(a, b, c, d, e)~ is called Olympic if all of the following conditions hold:

• ~l_a < l_b < r_a < r_b~

• ~l_d < l_e < r_d < r_e~

• ~l_c < r_b < l_d < r_c~

The beauty of an Olympic 5-tuple is equal to the sum of the beauties of its five intervals.

For each test case, find the maximum possible beauty of an Olympic ~5~-tuple. If no Olympic ~5~-tuple exists, print ~-1~.

Input

Each input contains multiple test cases. The first line contains ~t~ ~(1 \le t \le 10^5)~, the number of test cases.

The first line of each test case contains ~n~ ~(1 \le n \le 5\times 10^5)~, the number of intervals.

Each of the next ~n~ lines contains three integers ~l_i~, ~r_i~, and ~s_i~ ~(1 \le l_i \le r_i \le 5\times 10^5~, ~1 \le s_i \le 10^6)~, describing the endpoints and beauty of the ~i~-th interval.

It is guaranteed that the sum of ~n~ over all test cases does not exceed ~5\times 10^5~.

Output

For each test case, print a single integer: the maximum possible beauty of an Olympic 5-tuple, or ~-1~ if no such 5-tuple exists.

Examples

Input 1

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

Output 1

15
-1

Input 2

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

Output 2

32