VegiCat possède $n$ intervalles entiers fermés $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Il souhaite construire une suite $a_1, a_2, \ldots, a_n$ en choisissant un entier $a_i$ dans chaque intervalle $[l_i, r_i]$. Autrement dit, $l_i \le a_i \le r_i$ pour tout $1 \le i \le n$.

Une position $i$ est appelée une position de record si $a_i > a_j$ pour tout $1 \le j < i$. En particulier, la position $1$ est toujours une position de record.

Aidez VegiCat à minimiser le nombre de positions de record. Affichez ce nombre minimal.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 10^6$), le nombre d'intervalles.

La $i$-ème des $n$ lignes suivantes contient deux entiers $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), décrivant l'intervalle disponible à la position $i$.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez un entier — le nombre minimal possible de positions de record.

Exemples

Entrée 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

Sortie 1

2
4

Remarque

Dans le premier cas de test, une suite optimale est $a = [1, 100, 20, 30]$. Ses positions de record sont $1$ et $2$.

Dans le deuxième cas de test, une suite optimale est $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Ses positions de record sont $1, 2, 5$ et $7$. La position $8$ n'est pas un record car sa valeur est égale au maximum observé jusqu'alors.