宇宙からの異星人が（ついに！）地球に侵入しました。自分を守らなければ、分解されてしまいます！あるいは同化されるか、食べられるかもしれません。まだよく分かっていません。

異星人は既知のパターンに従って攻撃します。攻撃者は $n$ 体いて、$i$ 番目の攻撃者は時刻 $a_i$ に、あなたから距離 $d_i$ の位置に現れます。遅くとも時刻 $b_i$ までに倒さなければなりません。そうしないと武器を発射し、戦いは確実に終わってしまいます。

あなたの武器は範囲攻撃砲で、威力を任意に設定できます。威力 $R$ で発射すると、距離が $R$ 以下の異星人をすべて瞬時に倒します。また、燃料電池を $R$ 個消費します。

自分が殺されることなくすべての異星人を倒すための最小コスト（燃料電池の個数で測ります）を求めてください。

入力ファイルのサイズは 0.1 MiB 以下です。

入力

入力の最初の行にはテストケース数 $T$ が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には異星人の数 $n$（$1 \le n \le 300$）が与えられます。続く $n$ 行のうち $i$ 行目には、3 つの整数 $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

1
3
1 4 4
4 7 5
3 4 7

出力 1

7