Hay $n$ canguros en una recta numérica, donde el $i$-ésimo canguro se encuentra inicialmente en la coordenada positiva $c_i$ (es decir, $c_i > 0$), y tiene dos longitudes de paso $a_i$ y $b_i$.

Los canguros se controlan presionando los botones 1, 2, 3 y 4 del teclado. Todos los canguros se moverán simultáneamente según el botón presionado. Específicamente, sea $x_i$ la coordenada actual del $i$-ésimo canguro:

• Botón 1: Se moverá a $(x_i + a_i)$.
• Botón 2: Se moverá a $(x_i - a_i)$.
• Botón 3: Se moverá a $(x_i + b_i)$.
• Botón 4: Se moverá a $(x_i - b_i)$.

Está permitido que dos o más canguros estén en la misma coordenada. Si dos canguros se encuentran durante el movimiento, simplemente se atravesarán entre sí.

Puedes presionar los botones tantas veces como quieras. Maximiza el número de canguros con una coordenada negativa (es decir, maximiza el número de canguros con $x_i < 0$) después de las operaciones.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^5$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene un entero $n$ ($1 \le n \le 2 \times 10^5$) que indica el número de canguros.

En las siguientes $n$ líneas, la $i$-ésima línea contiene tres enteros $a_i$, $b_i$ y $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) que describen al $i$-ésimo canguro.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una línea con un entero, que indique el número máximo de canguros con una coordenada negativa después de las operaciones.

Ejemplos

Entrada 1

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

Salida 1

3
0