Det er $n$ kenguruer på en tallinje, der den $i$-te kenguruen til å begynne med befinner seg på den positive koordinaten $c_i$ (det vil si $c_i > 0$), og har to steglengder $a_i$ og $b_i$.

Kenguruene styres ved å trykke på knappene 1, 2, 3 og 4 på tastaturet. Alle kenguruene vil flytte seg samtidig i henhold til knappen som trykkes. Spesifikt, la $x_i$ være den nåværende koordinaten til den $i$-te kenguruen:

• Knapp 1: Den flytter seg til $(x_i + a_i)$.
• Knapp 2: Den flytter seg til $(x_i - a_i)$.
• Knapp 3: Den flytter seg til $(x_i + b_i)$.
• Knapp 4: Den flytter seg til $(x_i - b_i)$.

Det er tillatt for to eller flere kenguruer å være på samme koordinat. Hvis to kenguruer møtes under bevegelsen, vil de ganske enkelt passere gjennom hverandre.

Du kan trykke på knappene så mange ganger du vil. Maksimer antallet kenguruer med en negativ koordinat (det vil si maksimer antallet kenguruer med $x_i < 0$) etter operasjonene.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^5$) som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \times 10^5$) som angir antallet kenguruer.

I de følgende $n$ linjene inneholder den $i$-te linjen tre heltall $a_i$, $b_i$ og $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) som beskriver den $i$-te kenguruen.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder ett heltall som angir det maksimale antallet kenguruer med en negativ koordinat etter operasjonene.

Eksempler

Inndata 1

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

Utdata 1

3
0