There are $n$ events. Event $i$ has a deadline $d_i$, a color $c_i$, and a weight $w_i$. Every color occurs at most twice among the events.

You may choose any subset of the events and assign each chosen event to a positive integer day, so that all of the following hold:

• no two chosen events are assigned to the same day;
• if event $i$ is assigned to day $x$, then $x \le d_i$;
• if two consecutive days $x$ and $x+1$ both have an event assigned to them, those two events have different colors.

Days with no event assigned to them are allowed, and there is no limit on how large a day number may be. You may also choose no events at all, in which case the total weight is $0$.

Find the maximum possible total weight of the chosen events.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$): the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$): the number of events.

Each of the next $n$ lines contains three integers $d_i$, $c_i$, and $w_i$ ($1 \le d_i,c_i,w_i \le 10^9$): the deadline, the color, and the weight of the $i$-th event.

For every test case, each value occurs at most twice among $c_1,c_2,\ldots,c_n$. It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

Output

For each test case, print a single integer: the maximum possible total weight.

Examples

Input 1

5
2
1 1 100
2 1 99
2
2 1 16
3 1 4
4
2 1 37
1 2 37
2 2 12
1 1 60
7
4 3 13
2 3 3
1 1 28
6 2 30
4 1 16
5 2 21
3 4 37
10
6 3 27
5 4 8
3 5 27
2 2 11
1 5 6
1 1 33
6 3 28
1 4 32
6 2 21
2 1 30

Output 1

100
20
74
132
165

Note

In the first test case, the two events have the same color. Their deadlines do not leave an empty day between them, so at most one can be chosen; event $1$ has the larger weight.

In the second test case, assign the first event to day $1$ and the second event to day $3$. The empty day $2$ makes it possible to choose both events even though their colors are equal.

In the third test case, choose events $1$ and $2$ and assign them to days $2$ and $1$, respectively, for a total weight of $74$.

In the fourth test case, one optimal schedule uses events $3$, $4$, $7$, $5$, and $6$ on days $1$ through $5$, in that order. Its total weight is $28+30+37+16+21=132$. In particular, both occurrences of colors $1$ and $2$ are used, but equal colors are never placed on consecutive days.

In the fifth test case, one optimal schedule uses events $8$, $10$, $3$, $1$, $9$, and $7$ on days $1$ through $6$. Its total weight is $165$.