嚟自外太空嘅外星人（終於！）入侵地球喇。保護自己，否則你就會畀佢哋分解！或者同化。或者食咗。我哋暫時仲未肯定。

外星人會跟住一個已知嘅模式攻擊。總共有 $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