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

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

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

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

输入格式

输入的第一行包含测试用例的数量 $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$。

输入文件大小不超过 $0.1$ MiB。

输出格式

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

样例

输入 1

1
3
1 4 4
4 7 5
3 4 7

输出 1

7