Пришельцы из космоса (наконец-то!) вторглись на Землю. Защищайтесь, иначе вас дезинтегрируют! Или ассимилируют. Или съедят. Мы пока не уверены.

Пришельцы атакуют по известной схеме. Всего есть $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