外星人终于入侵地球了。保卫你自己，否则你就会被分解！或者被同化。或者被吃掉。我们还不确定。

外星人遵循一种已知的攻击模式。共有 $n$ 个攻击者，第 $i$ 个攻击者在时间 $a_i$ 出现，距离你 $d_i$。他必须在时间 $b_i$ 之前被消灭，否则他将发射武器，这肯定会结束战斗。

你的武器是一个区域爆破器，可以设置为任何给定的功率。如果以功率 $R$ 发射，它会瞬间摧毁所有距离为 $R$ 或更近的外星人。它同时消耗 $R$ 个燃料电池。

确定消灭所有外星人且不被杀死的最小成本（以燃料电池为单位）。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例的第一行包含外星人的数量 $n$ ($1 \leqslant n \leqslant 300$)。接下来的 $n$ 行中，第 $i$ 行包含三个整数 $a_i, b_i, d_i$ ($1 \leqslant a_i < b_i \leqslant 10\,000$; $1 \leqslant d_i \leqslant 10\,000$)。

第 $i$ 个外星人在时间 $a_i$ 出现，一直持续到时间 $b_i$，他与你的距离为 $d_i$。

输出格式

对于每个测试用例，输出一行，包含消灭所有外星人所需的最小燃料电池数量。

样例

样例输入 1

1
3
1 4 4
4 7 5
3 4 7

样例输出 1

7