Na osi liczbowej znajduje się $n$ kangurów, przy czym $i$-ty kangur znajduje się początkowo na dodatniej współrzędnej $c_i$ (to znaczy $c_i > 0$) oraz ma dwie długości skoku $a_i$ i $b_i$.

Kangurami steruje się, naciskając przyciski 1, 2, 3 oraz 4 na klawiaturze. Wszystkie kangury poruszają się jednocześnie zgodnie z naciśniętym przyciskiem. Dokładniej, niech $x_i$ będzie aktualną współrzędną $i$-tego kangura:

• Przycisk 1: Przemieszcza się na $(x_i + a_i)$.
• Przycisk 2: Przemieszcza się na $(x_i - a_i)$.
• Przycisk 3: Przemieszcza się na $(x_i + b_i)$.
• Przycisk 4: Przemieszcza się na $(x_i - b_i)$.

Dozwolone jest, aby dwa lub więcej kangurów znajdowało się na tej samej współrzędnej. Jeśli dwa kangury spotkają się podczas ruchu, po prostu przenikną przez siebie.

Możesz naciskać przyciski dowolnie wiele razy. Zmaksymalizuj liczbę kangurów o ujemnej współrzędnej (to znaczy zmaksymalizuj liczbę kangurów spełniających $x_i < 0$) po wykonaniu operacji.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \times 10^5$), oznaczającą liczbę kangurów.

W kolejnych $n$ wierszach $i$-ty wiersz zawiera trzy liczby całkowite $a_i$, $b_i$ oraz $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$), opisujące $i$-tego kangura.

Gwarantowane jest, że suma $n$ we wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą maksymalną liczbę kangurów o ujemnej współrzędnej po wykonaniu operacji.

Przykład

Wejście 1

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

Wyjście 1

3
0