$n$개의 행사가 있다. 행사 $i$에는 마감일 $d_i$, 색 $c_i$, 가중치 $w_i$가 있다. 각 색은 전체 행사에서 최대 두 번 등장한다.

행사들의 임의의 부분집합을 선택하고, 선택한 각 행사를 양의 정수로 나타내는 날짜에 배정할 수 있다. 이때 다음 조건을 모두 만족해야 한다.

• 선택한 두 행사를 같은 날짜에 배정할 수 없다.
• 행사 $i$를 날짜 $x$에 배정했다면 $x\le d_i$여야 한다.
• 연속한 두 날짜 $x$와 $x+1$에 모두 행사가 배정되어 있다면, 두 행사의 색은 달라야 한다.

아무 행사도 배정되지 않은 날짜가 있어도 되며, 날짜를 나타내는 수의 크기에는 제한이 없다. 아무 행사도 선택하지 않아도 되며, 이 경우 가중치의 합은 $0$이다.

선택한 행사들의 가중치 합의 최댓값을 구하여라.

입력

첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1\le t\le 1000$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에 행사의 수를 나타내는 정수 $n$ ($1\le n\le 200\,000$)이 주어진다.

다음 $n$개의 줄에는 각각 세 정수 $d_i$, $c_i$, $w_i$ ($1\le d_i,c_i,w_i\le 10^9$)가 주어진다. 이는 $i$번째 행사의 마감일, 색, 가중치를 나타낸다.

각 테스트 케이스에서 $c_1,c_2,\ldots,c_n$ 중 각 값은 최대 두 번 등장한다. 모든 테스트 케이스에 걸친 $n$의 합은 $200\,000$을 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 가중치 합의 최댓값을 나타내는 정수 하나를 출력한다.

예제

입력 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

출력 1

100
20
74
132
165

참고

첫 번째 테스트 케이스에서 두 행사의 색은 같다. 마감일 때문에 두 행사 사이에 빈 날짜를 둘 수 없으므로 최대 하나만 선택할 수 있다. 행사 $1$의 가중치가 더 크다.

두 번째 테스트 케이스에서는 첫 번째 행사를 날짜 $1$에, 두 번째 행사를 날짜 $3$에 배정한다. 날짜 $2$가 비어 있으므로 두 행사의 색이 같아도 둘 다 선택할 수 있다.

세 번째 테스트 케이스에서는 행사 $1$과 $2$를 선택하고 각각 날짜 $2$와 $1$에 배정하면 가중치의 합은 $74$이다.

네 번째 테스트 케이스에서 한 최적 일정은 행사 $3,4,7,5,6$을 이 순서대로 날짜 $1$부터 $5$까지 배정한다. 가중치의 합은 $28+30+37+16+21=132$이다. 특히 색 $1$과 $2$의 두 행사 모두 사용하지만, 같은 색을 연속한 날짜에 배정하는 일은 없다.

다섯 번째 테스트 케이스에서 한 최적 일정은 행사 $8,10,3,1,9,7$을 날짜 $1$부터 $6$까지 배정한다. 가중치의 합은 $165$이다.