Það eru $n$ kengúrur á talnalínu, þar sem $i$-ta kengúran er upphaflega í jákvæða hnitinu $c_i$ (það er, $c_i > 0$), og hefur tvær skrefalengdir $a_i$ og $b_i$.

Kengúrunum er stjórnað með því að ýta á hnappana 1, 2, 3 og 4 á lyklaborðinu. Allar kengúrurnar munu hreyfast samtímis í samræmi við hnappinn sem ýtt er á. Nánar tiltekið, látum $x_i$ vera núverandi hnit $i$-tu kengúrunnar:

• Hnappur 1: Hún færist í $(x_i + a_i)$.
• Hnappur 2: Hún færist í $(x_i - a_i)$.
• Hnappur 3: Hún færist í $(x_i + b_i)$.
• Hnappur 4: Hún færist í $(x_i - b_i)$.

Leyfilegt er að tvær eða fleiri kengúrur séu í sama hniti. Ef tvær kengúrur mætast á meðan á hreyfingunni stendur fara þær einfaldlega í gegnum hvor aðra.

Þú getur ýtt á hnappana eins oft og þú vilt. Hámarkaðu fjölda kengúra með neikvætt hnit (það er, hámarkaðu fjölda kengúra með $x_i < 0$) eftir aðgerðirnar.

Inntak

Það eru mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 10^5$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \times 10^5$) sem gefur til kynna fjölda kengúra.

Í næstu $n$ línum inniheldur $i$-ta línan þrjár heiltölur $a_i$, $b_i$ og $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) sem lýsa $i$-tu kengúrunni.

Tryggt er að summa $n$ í öllum prófunartilvikum fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu sem gefur til kynna hámarksfjölda kengúra með neikvætt hnit eftir aðgerðirnar.

Dæmi

Inntak 1

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

Úttak 1

3
0