有 $n$ 个事件。事件 $i$ 有一个截止日期 $d_i$、一种颜色 $c_i$ 和一个权值 $w_i$。每种颜色在这些事件中至多出现两次。

你可以选择这些事件的任意子集，并将每个选中的事件安排在一个正整数编号的日子，使以下所有条件成立：

• 任意两个选中的事件都不能安排在同一天；
• 如果事件 $i$ 被安排在第 $x$ 天，则 $x\le d_i$；
• 如果相邻的两天 $x$ 和 $x+1$ 都安排了事件，那么这两个事件的颜色必须不同。

允许某些日子不安排事件，且日子的编号大小没有上限。你也可以不选择任何事件，此时总权值为 $0$。

求选中事件的总权值的最大可能值。

输入格式

第一行包含一个整数 $t$ ($1\le t\le1000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1\le n\le200\,000$)，表示事件的数量。

接下来 $n$ 行，每行包含三个整数 $d_i$、$c_i$ 和 $w_i$ ($1\le d_i,c_i,w_i\le10^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$。