$n$ 個のイベントがあります。イベント $i$ には締切 $d_i$、色 $c_i$、重み $w_i$ があります。各色は、すべてのイベントの中で高々 2 回しか現れません。

イベントの任意の部分集合を選び、選んだ各イベントを正の整数で表される日に割り当てることができます。このとき、以下の条件をすべて満たす必要があります。

• 選んだ 2 つのイベントを同じ日に割り当てない。
• イベント $i$ を $x$ 日目に割り当てる場合、$x \le d_i$ を満たす。
• 連続する 2 日間、$x$ 日目と $x+1$ 日目の両方にイベントを割り当てる場合、それらのイベントの色は異なる。

イベントを割り当てない日があってもかまいません。また、日の番号の大きさに上限はありません。イベントをまったく選ばなくてもよく、その場合の重みの合計は $0$ です。

選んだイベントの重みの合計として達成できる最大値を求めてください。

入力

最初の行には、テストケースの数を表す整数 $t$（$1 \le t \le 1000$）が 1 つ与えられます。

各テストケースの最初の行には、イベントの数を表す整数 $n$（$1 \le n \le 200\,000$）が 1 つ与えられます。

続く $n$ 行のそれぞれには、イベント $i$ の締切、色、重みを表す 3 つの整数 $d_i,c_i,w_i$（$1 \le d_i,c_i,w_i \le 10^9$）が与えられます。

各テストケースにおいて、$c_1,c_2,\ldots,c_n$ の中に各値は高々 2 回しか現れません。すべてのテストケースにわたる $n$ の合計は $200\,000$ 以下であることが保証されます。

出力

各テストケースについて、達成できる重みの合計の最大値を表す整数を 1 つ出力してください。

入出力例

入力 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

注記

最初のテストケースでは、2 つのイベントの色は同じです。締切のため、それらの間に何も割り当てない日を設けることはできないので、高々 1 つしか選べません。イベント $1$ のほうが重みが大きいです。

2 番目のテストケースでは、最初のイベントを $1$ 日目に、2 番目のイベントを $3$ 日目に割り当てます。$2$ 日目に何も割り当てないことで、同じ色であっても両方のイベントを選ぶことができます。

3 番目のテストケースでは、イベント $1$ と $2$ を選び、それぞれ $2$ 日目と $1$ 日目に割り当てると、重みの合計は $74$ になります。

4 番目のテストケースでは、最適なスケジュールの一例は、イベント $3,4,7,5,6$ をこの順に $1$ 日目から $5$ 日目に割り当てるものです。重みの合計は $28+30+37+16+21=132$ です。特に、色 $1$ と $2$ のイベントはそれぞれ 2 回とも使われていますが、同じ色のイベントが連続する日に配置されることはありません。

5 番目のテストケースでは、最適なスケジュールの一例は、イベント $8,10,3,1,9,7$ を $1$ 日目から $6$ 日目に割り当てるものです。重みの合計は $165$ です。