Lukusuoralla on $n$ kengurua, missä $i$-s kenguru on aluksi positiivisessa koordinaatissa $c_i$ (eli $c_i > 0$), ja sillä on kaksi askelpituutta $a_i$ ja $b_i$.

Kenguruita ohjataan painamalla näppäimistön painikkeita 1, 2, 3 ja 4. Kaikki kengurut liikkuvat samanaikaisesti painetun painikkeen mukaan. Tarkemmin sanottuna, olkoon $x_i$ $i$-nnen kengurun nykyinen koordinaatti:

• Painike 1: Se siirtyy kohtaan $(x_i + a_i)$.
• Painike 2: Se siirtyy kohtaan $(x_i - a_i)$.
• Painike 3: Se siirtyy kohtaan $(x_i + b_i)$.
• Painike 4: Se siirtyy kohtaan $(x_i - b_i)$.

Kahden tai useamman kengurun on sallittua olla samassa koordinaatissa. Jos kaksi kengurua kohtaavat liikkeen aikana, ne vain kulkevat toistensa läpi.

Voit painaa painikkeita niin monta kertaa kuin haluat. Maksimoi negatiivisessa koordinaatissa olevien kenguruiden määrä (eli maksimoi niiden kenguruiden määrä, joilla $x_i < 0$) operaatioiden jälkeen.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmoittaa testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$), joka ilmoittaa kenguruiden lukumäärän.

Seuraavilla $n$ rivillä $i$-s rivi sisältää kolme kokonaislukua $a_i$, $b_i$ ja $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$), jotka kuvaavat $i$-ttä kengurua.

On taattu, että lukujen $n$ summa kaikissa testitapauksissa ei ylitä lukua $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää yhden kokonaisluvun: negatiivisessa koordinaatissa olevien kenguruiden enimmäismäärän operaatioiden jälkeen.

Esimerkit

Syöte 1

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

Tuloste 1

3
0