Nene entraîne son équipe en tant qu'entraîneuse de basket-ball. L'équipe de Nene se compose de $n$ joueurs, numérotés de $1$ à $n$. Le $i$-ème joueur possède un intervalle de bras $[l_i,r_i]$. Deux joueurs $i$ et $j$ ($i \neq j$) peuvent se passer le ballon si et seulement si $|i-j|\in[l_i+l_j,r_i+r_j]$ (ici, $|x|$ désigne la valeur absolue de $x$).

Nene souhaite tester la capacité de coopération de ces joueurs. Pour ce faire, elle organisera plusieurs sessions d'évaluation.

• À chaque session, Nene sélectionne une séquence de joueurs $p_1,p_2,\ldots,p_m$ telle que les joueurs $p_i$ et $p_{i+1}$ puissent se passer le ballon pour tout $1 \le i < m$. La longueur de la séquence $m$ peut être choisie par Nene. Chaque joueur peut apparaître dans la séquence $p_1,p_2,\ldots,p_m$ plusieurs fois ou ne pas y apparaître du tout.
• Ensuite, Nene lance un ballon au joueur $p_1$, le joueur $p_1$ passe le ballon au joueur $p_2$, et ainsi de suite... Le joueur $p_m$ lance le ballon hors du terrain de basket-ball, de sorte qu'il ne puisse plus être utilisé.

En tant qu'entraîneuse, Nene veut que chacun des $n$ joueurs apparaisse dans au moins une session d'évaluation. Comme Nene a un rendez-vous après l'école, elle vous demande de calculer le nombre minimum de sessions d'évaluation nécessaires pour accomplir cette tâche.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 2\cdot 10^5$). La description des cas de test suit.

La première ligne contient un entier unique $n$ ($1 \le n \le 2\cdot 10^6$) — le nombre de joueurs.

La $i$-ème des $n$ lignes suivantes contient deux entiers $l_i$ et $r_i$ ($1\leq l_i\leq r_i\leq n$) — l'intervalle de bras du $i$-ème joueur.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2\cdot 10^6$.

Sortie

Pour chaque cas de test, affichez un entier — le nombre minimum de sessions d'évaluation dont Nene a besoin pour terminer son travail.

Exemples

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

Sortie 1

2
2
2
1
3

Remarque

Dans les deux premiers cas de test, Nene peut organiser deux sessions d'évaluation : une avec $p=[1]$ et une avec $p=[2]$. Il peut être démontré qu'organiser une seule session d'évaluation n'est pas suffisant, donc la réponse est $2$.

Dans le troisième cas de test, Nene peut organiser deux sessions d'évaluation : une avec $p=[1,3]$ et une avec $p=[2]$. Le joueur $1$ peut passer le ballon au joueur $3$ car $|3-1|=2 \in [1+1,3+3]$. Il peut être démontré qu'organiser une seule session d'évaluation n'est pas suffisant, donc la réponse est $2$.