來自外太空的外星人（終於！）入侵地球了。保護自己，否則就會被分解！或是被同化。或是被吃掉。我們還不確定。

外星人的攻擊遵循已知的模式。共有 $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