Die Außerirdischen aus dem Weltall haben (endlich!) die Erde überfallen. Verteidige dich, oder du wirst desintegriert! Oder assimiliert. Oder gefressen. Wir sind uns noch nicht sicher.

Die Außerirdischen folgen einem bekannten Angriffsmuster. Es gibt $n$ Angreifer; der $i$-te erscheint zum Zeitpunkt $a_i$ in einer Entfernung $d_i$ von dir. Er muss spätestens zum Zeitpunkt $b_i$ zerstört werden, sonst feuert er seine Waffe ab, was den Kampf garantiert beendet.

Deine Waffe ist ein Flächenstrahler, dessen Stärke beliebig eingestellt werden kann. Ein Schuss mit Stärke $R$ zerstört augenblicklich alle Außerirdischen in einer Entfernung von höchstens $R$. Er verbraucht außerdem $R$ Brennstoffzellen.

Bestimme die minimalen Kosten (gemessen in Brennstoffzellen), um alle Außerirdischen zu zerstören, ohne getötet zu werden.

Die Größe der Eingabedatei überschreitet 0.1 MiB nicht.

Eingabe

Die erste Eingabezeile enthält die Anzahl der Testfälle $T$. Es folgen die Beschreibungen der Testfälle:

Jeder Testfall beginnt mit einer Zeile mit der Anzahl der Außerirdischen $n$ ($1 \le n \le 300$). Von den nächsten $n$ Zeilen enthält die $i$-te drei ganze Zahlen $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). Der $i$-te Außerirdische erscheint zum Zeitpunkt $a_i$, bleibt bis $b_i$ untätig und ist $d_i$ von dir entfernt.

Ausgabe

Gib für jeden Testfall eine Zeile mit der minimalen Anzahl an Zellen aus, die zur Zerstörung aller Außerirdischen benötigt wird.

Beispiele

Eingabe 1

1
3
1 4 4
4 7 5
3 4 7

Ausgabe 1

7