Il y a $n$ kangourous sur une droite graduée, où le $i$-ème kangourou se trouve initialement à la coordonnée positive $c_i$ (c'est-à-dire $c_i > 0$), et possède deux longueurs de pas $a_i$ et $b_i$.

Les kangourous sont contrôlés en appuyant sur les touches 1, 2, 3 et 4 du clavier. Tous les kangourous se déplacent simultanément selon la touche pressée. Plus précisément, soit $x_i$ la coordonnée actuelle du $i$-ème kangourou :

• Touche 1 : il se déplace en $(x_i + a_i)$.
• Touche 2 : il se déplace en $(x_i - a_i)$.
• Touche 3 : il se déplace en $(x_i + b_i)$.
• Touche 4 : il se déplace en $(x_i - b_i)$.

Il est permis que deux kangourous ou plus se trouvent à la même coordonnée. Si deux kangourous se croisent pendant le déplacement, ils se traversent simplement l'un l'autre.

Vous pouvez appuyer sur les touches autant de fois que vous le souhaitez. Maximisez le nombre de kangourous ayant une coordonnée strictement négative (c'est-à-dire maximisez le nombre de kangourous tels que $x_i < 0$) après les opérations.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient un entier $n$ ($1 \le n \le 2 \times 10^5$) indiquant le nombre de kangourous.

Pour les $n$ lignes suivantes, la $i$-ème ligne contient trois entiers $a_i$, $b_i$ et $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) décrivant le $i$-ème kangourou.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un entier, indiquant le nombre maximum de kangourous ayant une coordonnée négative après les opérations.

Exemples

Entrée 1

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

Sortie 1

3
0