Es befinden sich $n$ Kängurus auf einer Zahlengeraden, wobei sich das $i$-te Känguru anfangs bei der positiven Koordinate $c_i$ befindet (das heißt $c_i > 0$) und zwei Schrittlängen $a_i$ und $b_i$ besitzt.

Die Kängurus werden durch Drücken der Tasten 1, 2, 3 und 4 auf der Tastatur gesteuert. Alle Kängurus bewegen sich gleichzeitig entsprechend der gedrückten Taste. Sei konkret $x_i$ die aktuelle Koordinate des $i$-ten Kängurus:

• Taste 1: Es bewegt sich zu $(x_i + a_i)$.
• Taste 2: Es bewegt sich zu $(x_i - a_i)$.
• Taste 3: Es bewegt sich zu $(x_i + b_i)$.
• Taste 4: Es bewegt sich zu $(x_i - b_i)$.

Es ist erlaubt, dass sich zwei oder mehr Kängurus an derselben Koordinate befinden. Wenn sich zwei Kängurus während der Bewegung begegnen, laufen sie einfach durcheinander hindurch.

Du kannst die Tasten beliebig oft drücken. Maximiere die Anzahl der Kängurus mit einer negativen Koordinate (das heißt, maximiere die Anzahl der Kängurus mit $x_i < 0$) nach den Operationen.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \times 10^5$), die die Anzahl der Kängurus angibt.

In den folgenden $n$ Zeilen enthält die $i$-te Zeile drei ganze Zahlen $a_i$, $b_i$ und $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$), die das $i$-te Känguru beschreiben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit einer einzigen ganzen Zahl aus, die die maximale Anzahl der Kängurus mit einer negativen Koordinate nach den Operationen angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

3
0