Прибульці з космосу (нарешті!) вторглися на Землю. Захищайтеся, інакше вас дезінтегрують! Або асимілюють. Або з’їдять. Ми ще не впевнені.

Прибульці атакують за відомою схемою. Є $n$ нападників; $i$-й з’являється в момент $a_i$ на відстані $d_i$ від вас. Його потрібно знищити не пізніше моменту $b_i$, інакше він вистрелить зі своєї зброї, що неодмінно завершить бій.

Ваша зброя — бластер площинної дії, потужність якого можна встановити довільно. Постріл із потужністю $R$ миттєво знищує всіх прибульців на відстані не більш ніж $R$. Він також витрачає $R$ паливних елементів.

Визначте мінімальну вартість (у паливних елементах) знищення всіх прибульців так, щоб вас не вбили.

Розмір вхідного файлу не перевищує 0.1 MiB.

Вхідні дані

Перший рядок вхідних даних містить кількість тестових випадків $T$. Далі наведено їхні описи:

Кожен тестовий випадок починається з рядка, що містить кількість прибульців $n$ ($1 \le n \le 300$). Серед наступних $n$ рядків $i$-й містить три цілі числа $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). $i$-й прибулець з’являється в момент $a_i$, не діє до $b_i$, а його відстань до вас дорівнює $d_i$.

Вихідні дані

Для кожного тестового випадку виведіть один рядок із мінімальною кількістю елементів, потрібних для знищення всіх прибульців.

Приклади

Вхідні дані 1

1
3
1 4 4
4 7 5
3 4 7

Вихідні дані 1

7