题目背景

外太空的外星人们（终于！）入侵了地球。保卫你自己，否则就会四分五裂！或者是被吸收。或者是被吃掉。我们还不很确定。

题目描述

外星人们遵循一个已知的攻击模式。有 $n$ 个攻击者，第 $i$ 个在 $a_i$ 的时间内出现，在距离你 $d_i$ 远的地方。你必须在时间 $b_i$ 前消灭他，否则他就会开火，那战斗就肯定结束了。

你的武器是一个范围冲击波生成器，可以任意调节其能量。如果将能量设置成 $R$，它就会消灭目前距离你不超过 $R$ 的所有的外星人。它同时消耗 $R$ 块燃料电池。在不被杀死的前提下，确定消灭所有外星人的最小花费（以燃料电池数计）。

输入格式

输入的第一行包含一个整数 $T$，表示数据组数。每一组数据的格式如下：

每组数据的第一行包含一个整数 $n$，表示外星人个数；
接下来 $n$ 行每行包含 3 个整数 $a_i,b_i,d_i$，分别表示第 $i$ 个外星人的出现时间、需要被消灭的最晚时间、离你的距离。

输出格式

对于每组测试数据，分别输出一行一个整数，表示消灭所有外星人需要耗费的最小能量。

1
3
1 4 4
4 7 5
3 4 7

7

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le T\le 250$，$1\le n\le 300$，$1\le a_i< b_i\le 10^4$，$1\le d_i\le 10^4$。

题目来源

ACM ICPC 2014-2015 Central European Regional Contest, Problem L