มีจิงโจ้ $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