Det finns $n$ kängurur på en tallinje, där den $i$-te kängurun ursprungligen befinner sig på den positiva koordinaten $c_i$ (det vill säga $c_i > 0$), och har två steglängder $a_i$ och $b_i$.

Kängururna styrs genom att man trycker på knapparna 1, 2, 3 och 4 på tangentbordet. Alla kängurur förflyttar sig samtidigt enligt den knapp som trycks ned. Specifikt, låt $x_i$ vara den aktuella koordinaten för den $i$-te kängurun:

• Knapp 1: Den flyttar sig till $(x_i + a_i)$.
• Knapp 2: Den flyttar sig till $(x_i - a_i)$.
• Knapp 3: Den flyttar sig till $(x_i + b_i)$.
• Knapp 4: Den flyttar sig till $(x_i - b_i)$.

Det är tillåtet för två eller fler kängurur att befinna sig på samma koordinat. Om två kängurur möts under förflyttningen passerar de helt enkelt rakt igenom varandra.

Du får trycka på knapparna hur många gånger du vill. Maximera antalet kängurur med en negativ koordinat (det vill säga maximera antalet kängurur med $x_i < 0$) efter operationerna.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^5$) som anger antalet testfall. För varje testfall:

Den första raden innehåller ett heltal $n$ ($1 \le n \le 2 \times 10^5$) som anger antalet kängurur.

På de följande $n$ raderna innehåller den $i$-te raden tre heltal $a_i$, $b_i$ och $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) som beskriver den $i$-te kängurun.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett heltal som anger det maximala antalet kängurur med en negativ koordinat efter operationerna.

Exempel

Indata 1

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

Utdata 1

3
0