החייזרים מהחלל החיצון פלשו (סוף סוף!) לכדור הארץ. הגן על עצמך, אחרת תפורק לחלקיקים! או תוטמע בתוכם. או תיאכל. אנחנו עדיין לא בטוחים.

החייזרים פועלים לפי דפוס תקיפה ידוע. יש $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