لقد غزا الفضائيون القادمون من الفضاء الخارجي الأرض (أخيرًا!). دافع عن نفسك وإلا فستُفكَّك! أو تُستوعَب ضمنهم. أو تؤكل. لسنا متأكدين بعد.

يتبع الفضائيون نمط هجوم معروفًا. يوجد $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