Les extraterrestres venus de l’espace ont (enfin !) envahi la Terre. Défendez-vous, ou vous serez désintégré ! Ou assimilé. Ou dévoré. Nous n’en sommes pas encore certains.

Les extraterrestres suivent un schéma d’attaque connu. Il y a $n$ attaquants ; le $i$-ième apparaît à l’instant $a_i$, à une distance $d_i$ de vous. Il doit être détruit au plus tard à l’instant $b_i$, sinon il tirera avec son arme, ce qui mettra assurément fin au combat.

Votre arme est un canon à effet de zone, réglable à n’importe quelle puissance. Un tir de puissance $R$ détruit instantanément tous les extraterrestres situés à une distance inférieure ou égale à $R$. Il consomme également $R$ piles à combustible.

Déterminez le coût minimal (mesuré en piles à combustible) pour détruire tous les extraterrestres sans vous faire tuer.

La taille du fichier d’entrée ne dépasse pas 0.1 MiB.

Entrée

La première ligne de l’entrée contient le nombre de cas de test $T$. Les descriptions des cas suivent :

Chaque cas commence par une ligne contenant le nombre d’extraterrestres $n$ ($1 \le n \le 300$). Parmi les $n$ lignes suivantes, la $i$-ième contient trois entiers $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$ ; $1 \le d_i \le 10\,000$). Le $i$-ième extraterrestre apparaît à l’instant $a_i$, reste inactif jusqu’à $b_i$ et se trouve à une distance $d_i$ de vous.

Sortie

Pour chaque cas de test, affichez une ligne contenant le nombre minimal de piles nécessaires pour détruire tous les extraterrestres.

Exemples

Entrée 1

1
3
1 4 4
4 7 5
3 4 7

Sortie 1

7