Nene está entrenando a su equipo como entrenadora de baloncesto. El equipo de Nene consta de $n$ jugadores, numerados del $1$ al $n$. El jugador $i$-ésimo tiene un intervalo de alcance $[l_i,r_i]$. Dos jugadores $i$ y $j$ ($i \neq j$) pueden pasarse el balón entre sí si y solo si $|i-j|\in[l_i+l_j,r_i+r_j]$ (aquí, $|x|$ denota el valor absoluto de $x$).

Nene quiere poner a prueba la capacidad de cooperación de estos jugadores. Para ello, llevará a cabo varias rondas de evaluación.

• En cada ronda, Nene seleccionará una secuencia de jugadores $p_1,p_2,\ldots,p_m$ tal que los jugadores $p_i$ y $p_{i+1}$ puedan pasarse el balón entre sí para todo $1 \le i < m$. La longitud de la secuencia $m$ puede ser elegida por Nene. Cada jugador puede aparecer en la secuencia $p_1,p_2,\ldots,p_m$ varias veces o no aparecer en absoluto.
• Luego, Nene lanzará un balón al jugador $p_1$, el jugador $p_1$ pasará el balón al jugador $p_2$ y así sucesivamente... El jugador $p_m$ lanzará el balón fuera de la cancha de baloncesto para que ya no pueda ser utilizado.

Como entrenadora, Nene quiere que cada uno de los $n$ jugadores aparezca en al menos una ronda de evaluación. Dado que Nene tiene una cita después de la escuela, quiere que calcules el número mínimo de rondas de evaluación necesarias para completar la tarea.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 2\cdot 10^5$). A continuación se presenta la descripción de los casos de prueba.

La primera línea contiene un único entero $n$ ($1 \le n \le 2\cdot 10^6$) — el número de jugadores.

La $i$-ésima de las siguientes $n$ líneas contiene dos enteros $l_i$ y $r_i$ ($1\leq l_i\leq r_i\leq n$) — el intervalo de alcance del jugador $i$-ésimo.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2\cdot 10^6$.

Salida

Para cada caso de prueba, imprime un entero — el número mínimo de rondas de evaluación que Nene necesita para completar su trabajo.

Ejemplos

Entrada 1

5
2
1 1
1 1
2
1 1
2 2
3
1 3
1 3
1 3
5
1 1
2 2
1 5
2 2
1 1
6
1 2
5 5
2 3
2 3
2 2
1 2

Salida 1

2
2
2
1
3

Nota

En los dos primeros casos de prueba, Nene puede organizar dos rondas de evaluación: una con $p=[1]$ y otra con $p=[2]$. Se puede demostrar que organizar una sola ronda de evaluación no es suficiente, por lo que la respuesta es $2$.

En el tercer caso de prueba, Nene puede organizar dos rondas de evaluación: una con $p=[1,3]$ y otra con $p=[2]$. El jugador $1$ puede pasar el balón al jugador $3$ ya que $|3-1|=2 \in [1+1,3+3]$. Se puede demostrar que organizar una sola ronda de evaluación no es suficiente, por lo que la respuesta es $2$.