Os alienígenas do espaço sideral (finalmente!) invadiram a Terra. Defenda-se ou será desintegrado! Ou assimilado. Ou devorado. Ainda não temos certeza.

Os alienígenas seguem um padrão de ataque conhecido. Há $n$ atacantes; o $i$-ésimo aparece no instante $a_i$, a uma distância $d_i$ de você. Ele deve ser destruído no máximo até o instante $b_i$; caso contrário, disparará sua arma, o que certamente encerrará a luta.

Sua arma é um canhão de área, que pode ser ajustado para qualquer potência. Ao disparar com potência $R$, ele destrói instantaneamente todos os alienígenas a uma distância menor ou igual a $R$. Também consome $R$ células de combustível.

Determine o custo mínimo (medido em células de combustível) para destruir todos os alienígenas sem ser morto.

O tamanho do arquivo de entrada não excede 0.1 MiB.

Entrada

A primeira linha da entrada contém o número de casos de teste $T$. Seguem as descrições dos casos:

Cada caso começa com uma linha contendo o número de alienígenas $n$ ($1 \le n \le 300$). Das próximas $n$ linhas, a $i$-ésima contém três inteiros $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). O $i$-ésimo alienígena aparece no instante $a_i$, fica inativo até $b_i$ e está a uma distância $d_i$ de você.

Saída

Para cada caso de teste, imprima uma linha contendo o número mínimo de células necessárias para destruir todos os alienígenas.

Exemplos

Entrada 1

1
3
1 4 4
4 7 5
3 4 7

Saída 1

7