ישנם $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