VegiCat tiene $n$ intervalos cerrados de números enteros $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Quiere construir una secuencia $a_1, a_2, \ldots, a_n$ eligiendo un entero $a_i$ de cada intervalo $[l_i, r_i]$. Es decir, $l_i \le a_i \le r_i$ para todo $1 \le i \le n$.

Una posición $i$ se llama posición de récord si $a_i > a_j$ para todo $1 \le j < i$. En particular, la posición $1$ es siempre una posición de récord.

Ayuda a VegiCat a minimizar el número de posiciones de récord. Imprime este número mínimo.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 10^6$), el número de intervalos.

La $i$-ésima de las siguientes $n$ líneas contiene dos enteros $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), que describen el intervalo disponible en la posición $i$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime un entero: el mínimo número posible de posiciones de récord.

Ejemplos

Entrada 1

2
4
1 1
1 100
20 20
30 30
8
-3 -1
-5 4
0 1
2 2
1 8
5 6
10 12
12 12

Salida 1

2
4

Nota

En el primer caso de prueba, una secuencia óptima es $a = [1, 100, 20, 30]$. Sus posiciones de récord son $1$ y $2$.

En el segundo caso de prueba, una secuencia óptima es $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Sus posiciones de récord son $1, 2, 5$ y $7$. La posición $8$ no es un récord porque su valor es igual al máximo visto hasta ese momento.