Bessie, la vaca, tiene ~N~ tareas que puedes completar. La i-ésima tarea, ~s_i~ decides completarla, debe comenzarse en o antes del tiempo ~s_i~ y tarda ~t_i~ tiempo en completarse .

¿Cuál es el número máximo de tareas que puedes completar? El tiempo comienza en 0, y una vez que comienzas una tarea, debes trabajar en ella hasta completarla, sin comenzar ninguna otra tarea mientras tanto.

Entrada

La primera línea contiene ~T~, el número de casos de prueba independientes. Cada caso de prueba tiene el siguiente formato.

• La primera línea contiene ~N~.
• Cada una de las siguientes ~N~ líneas contiene dos enteros, ~s_i~ y ~t_i~. La fila i+1 contiene los detalles del i-ésimo trabajo.

Se garantiza que la suma de ~N~ en todos los casos de prueba no supera ~3 \cdot 10^5~.

Salida

Para cada caso de prueba, el número máximo de trabajos que puede completar, en una nueva línea.

Restricciones

• ~1 \leq N \leq 2 \cdot 10^5~
• ~0 \leq s_i \leq 10^{18}~
• ~1 \leq t_i \leq 10^{18}~
• ~1 \leq T \leq 10~

Ejemplo de Entrada

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2

Ejemplo de Salida

1
2
2

Para el primer caso de prueba, solo puede completar uno de los trabajos. Tras completar un trabajo, será el tiempo 2 o posterior, por lo que será demasiado tarde para iniciar el otro trabajo, que debe iniciarse en el tiempo 1 o antes.

Para el segundo caso de prueba, puede iniciar el segundo trabajo en el tiempo 0 y finalizarlo en el tiempo 2, y luego iniciar el primer trabajo en el tiempo 2 y finalizarlo en el tiempo 5.

Calificación

Entradas	Restricciones adicionales
2	Dentro del mismo caso de prueba, todos los ~t_i~ son iguales.
3-4	~N \leq 2000~, ~s_i, t_i \leq 2000~
5-8	~N \leq 2000~
9-16	Sin restricciones adicionales.

USACO 2024 December Contest, Gold Problem 3. Job Completion.