Kosmici z przestrzeni kosmicznej (wreszcie!) najechali Ziemię. Broń się albo zostaniesz zdezintegrowany! Albo zasymilowany. Albo zjedzony. Jeszcze nie jesteśmy pewni.

Kosmici atakują według znanego schematu. Jest $n$ napastników; $i$-ty pojawia się w chwili $a_i$, w odległości $d_i$ od ciebie. Musi zostać zniszczony najpóźniej w chwili $b_i$, inaczej wystrzeli ze swojej broni, co z pewnością zakończy walkę.

Twoją bronią jest działo obszarowe, którego moc można ustawić dowolnie. Wystrzał z mocą $R$ natychmiast niszczy wszystkich kosmitów w odległości nie większej niż $R$. Zużywa też $R$ ogniw paliwowych.

Wyznacz minimalny koszt (mierzony liczbą ogniw paliwowych) zniszczenia wszystkich kosmitów bez utraty życia.

Rozmiar pliku wejściowego nie przekracza 0.1 MiB.

Wejście

Pierwszy wiersz wejścia zawiera liczbę przypadków testowych $T$. Dalej następują ich opisy:

Każdy przypadek zaczyna się od wiersza zawierającego liczbę kosmitów $n$ ($1 \le n \le 300$). Wśród następnych $n$ wierszy $i$-ty zawiera trzy liczby całkowite $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). $i$-ty kosmita pojawia się w chwili $a_i$, pozostaje bezczynny do $b_i$, a jego odległość od ciebie wynosi $d_i$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający minimalną liczbę ogniw potrzebnych do zniszczenia wszystkich kosmitów.

Przykład

Wejście 1

1
3
1 4 4
4 7 5
3 4 7

Wyjście 1

7