يوجد $n$ كنغر على خط الأعداد، حيث يقع الكنغر رقم $i$ في البداية عند الإحداثي الموجب $c_i$ (أي أن $c_i > 0$)، ويمتلك طولي خطوة $a_i$ و $b_i$.

يتم التحكم في الكناغر عن طريق الضغط على الأزرار 1 و 2 و 3 و 4 على لوحة المفاتيح. ستتحرك جميع الكناغر في وقت واحد وفقاً للزر المضغوط. وتحديداً، ليكن $x_i$ هو الإحداثي الحالي للكنغر رقم $i$:

• الزر 1: سينتقل إلى $(x_i + a_i)$.
• الزر 2: سينتقل إلى $(x_i - a_i)$.
• الزر 3: سينتقل إلى $(x_i + b_i)$.
• الزر 4: سينتقل إلى $(x_i - b_i)$.

يُسمح بوجود كنغرين أو أكثر عند نفس الإحداثي. إذا التقى كنغران أثناء الحركة، فإنهما ببساطة يمران عبر بعضهما البعض.

يمكنك الضغط على الأزرار بالقدر الذي تريده من المرات. عظّم عدد الكناغر ذات الإحداثي السالب (أي عظّم عدد الكناغر التي تحقق $x_i < 0$) بعد العمليات.

الإدخال

توجد حالات اختبار متعددة. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 10^5$) يشير إلى عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول على عدد صحيح $n$ ($1 \le n \le 2 \times 10^5$) يشير إلى عدد الكناغر.

في الأسطر الـ $n$ التالية، يحتوي السطر رقم $i$ على ثلاثة أعداد صحيحة $a_i$ و $b_i$ و $c_i$ ($-10^9 \le a_i, b_i \le 10^9$، $1 \le c_i \le 10^9$) تصف الكنغر رقم $i$.

من المضمون أن مجموع $n$ لجميع حالات الاختبار لا يتجاوز $2 \times 10^5$.

الإخراج

لكل حالة اختبار، اطبع سطراً واحداً يحتوي على عدد صحيح واحد، يشير إلى أكبر عدد من الكناغر ذات الإحداثي السالب بعد العمليات.

أمثلة

الإدخال 1

2
4
1 1 1
-1 3 4
0 -2 7
-5 0 10
1
0 0 1

الإخراج 1

3
0