Ci sono $n$ canguri su una retta numerica, dove l'$i$-esimo canguro si trova inizialmente alla coordinata positiva $c_i$ (cioè $c_i > 0$), e ha due lunghezze di passo $a_i$ e $b_i$.

I canguri sono controllati premendo i pulsanti 1, 2, 3 e 4 sulla tastiera. Tutti i canguri si muoveranno simultaneamente in base al pulsante premuto. Nello specifico, sia $x_i$ la coordinata attuale dell'$i$-esimo canguro:

• Pulsante 1: Si sposterà in $(x_i + a_i)$.
• Pulsante 2: Si sposterà in $(x_i - a_i)$.
• Pulsante 3: Si sposterà in $(x_i + b_i)$.
• Pulsante 4: Si sposterà in $(x_i - b_i)$.

È consentito che due o più canguri si trovino alla stessa coordinata. Se due canguri si incontrano durante il movimento, si passeranno semplicemente attraverso.

Puoi premere i pulsanti quante volte vuoi. Massimizza il numero di canguri con una coordinata negativa (cioè massimizza il numero di canguri con $x_i < 0$) dopo le operazioni.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^5$) che indica il numero di casi di test. Per ciascun caso di test:

La prima riga contiene un intero $n$ ($1 \le n \le 2 \times 10^5$) che indica il numero di canguri.

Per le successive $n$ righe, la $i$-esima riga contiene tre interi $a_i$, $b_i$ e $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) che descrivono l'$i$-esimo canguro.

È garantito che la somma di $n$ su tutti i casi di test non superi $2 \times 10^5$.

Output

Per ciascun caso di test, stampa una riga contenente un intero, che indica il numero massimo di canguri con una coordinata negativa dopo le operazioni.

Esempi

Input 1

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

Output 1

3
0