Hay $n$ eventos. El evento $i$ tiene una fecha límite $d_i$, un color $c_i$ y un peso $w_i$. Cada color aparece como máximo dos veces entre los eventos.

Puedes elegir cualquier subconjunto de los eventos y asignar cada evento elegido a un día cuyo número sea un entero positivo, de modo que se cumpla todo lo siguiente:

• No se asignan dos eventos elegidos al mismo día.
• Si el evento $i$ se asigna al día $x$, entonces $x \le d_i$.
• Si dos días consecutivos $x$ y $x + 1$ tienen ambos un evento asignado, esos dos eventos tienen colores diferentes.

Se permiten días sin ningún evento asignado, y no hay límite para lo grande que puede ser el número de un día. También puedes no elegir ningún evento, en cuyo caso el peso total es $0$.

Encuentra el máximo peso total posible de los eventos elegidos.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 1000$): el número de casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($1 \le n \le 200\,000$): el número de eventos.

Cada una de las siguientes $n$ líneas contiene tres enteros $d_i$, $c_i$ y $w_i$ ($1 \le d_i, c_i, w_i \le 10^9$): la fecha límite, el color y el peso del evento $i$.

Para cada caso de prueba, cada valor aparece como máximo dos veces entre $c_1, c_2, \ldots, c_n$. Se garantiza que la suma de $n$ en todos los casos de prueba no supera $200\,000$.

Salida

Para cada caso de prueba, imprime un único entero: el máximo peso total posible.

Ejemplos

Entrada 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

Salida 1

100
20
74
132
165

Nota

En el primer caso de prueba, los dos eventos tienen el mismo color. Sus fechas límite no dejan un día vacío entre ellos, por lo que se puede elegir como máximo uno; el evento $1$ tiene el mayor peso.

En el segundo caso de prueba, asigna el primer evento al día $1$ y el segundo evento al día $3$. El día vacío $2$ permite elegir ambos eventos aunque sus colores sean iguales.

En el tercer caso de prueba, elige los eventos $1$ y $2$ y asígnalos a los días $2$ y $1$, respectivamente, para obtener un peso total de $74$.

En el cuarto caso de prueba, una planificación óptima utiliza los eventos $3$, $4$, $7$, $5$ y $6$ en los días del $1$ al $5$, en ese orden. Su peso total es $28 + 30 + 37 + 16 + 21 = 132$. En particular, se utilizan ambas apariciones de los colores $1$ y $2$, pero nunca se colocan colores iguales en días consecutivos.

En el quinto caso de prueba, una planificación óptima utiliza los eventos $8$, $10$, $3$, $1$, $9$ y $7$ en los días del $1$ al $6$. Su peso total es $165$.