Nene trenuje swój zespół jako trener koszykówki. Zespół Nene składa się z $n$ zawodników, ponumerowanych od $1$ do $n$. $i$-ty zawodnik posiada przedział zasięgu ramion $[l_i,r_i]$. Dwaj zawodnicy $i$ oraz $j$ ($i \neq j$) mogą podawać sobie piłkę wtedy i tylko wtedy, gdy $|i-j|\in[l_i+l_j,r_i+r_j]$ (gdzie $|x|$ oznacza wartość bezwzględną $x$).

Nene chce przetestować zdolność współpracy tych zawodników. W tym celu przeprowadzi kilka rund oceny.

• W każdej rundzie Nene wybierze ciąg zawodników $p_1,p_2,\ldots,p_m$ taki, że zawodnicy $p_i$ oraz $p_{i+1}$ mogą podawać sobie piłkę dla każdego $1 \le i < m$. Długość ciągu $m$ może zostać wybrana przez Nene. Każdy zawodnik może pojawić się w ciągu $p_1,p_2,\ldots,p_m$ wielokrotnie lub nie pojawić się w nim wcale.
• Następnie Nene rzuci piłkę do zawodnika $p_1$, zawodnik $p_1$ poda piłkę do zawodnika $p_2$ i tak dalej... Zawodnik $p_m$ wyrzuci piłkę poza boisko, przez co nie będzie można jej już użyć.

Jako trener, Nene chce, aby każdy z $n$ zawodników pojawił się w co najmniej jednej rundzie oceny. Ponieważ Nene musi iść na randkę po szkole, chce, abyś obliczył minimalną liczbę rund oceny potrzebną do wykonania tego zadania.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $t$ ($1 \le t \le 2\cdot 10^5$). Następnie następuje opis przypadków testowych.

Pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 2\cdot 10^6$) — liczbę zawodników.

$i$-ta z kolejnych $n$ linii zawiera dwie liczby całkowite $l_i$ oraz $r_i$ ($1\leq l_i\leq r_i\leq n$) — przedział zasięgu ramion $i$-tego zawodnika.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $2\cdot 10^6$.

Wyjście

Dla każdego przypadku testowego wyprowadź jedną liczbę całkowitą — minimalną liczbę rund oceny, których Nene potrzebuje do wykonania swojej pracy.

Przykład

Wejście 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

Wyjście 1

2
2
2
1
3

Uwagi

W pierwszych dwóch przypadkach testowych Nene może przeprowadzić dwie rundy oceny: jedną z $p=[1]$ i jedną z $p=[2]$. Można wykazać, że przeprowadzenie jednej rundy oceny nie wystarczy, więc odpowiedzią jest $2$.

W trzecim przypadku testowym Nene może przeprowadzić dwie rundy oceny: jedną z $p=[1,3]$ i jedną z $p=[2]$. Zawodnik $1$ może podać piłkę do zawodnika $3$, ponieważ $|3-1|=2 \in [1+1,3+3]$. Można wykazać, że przeprowadzenie jednej rundy oceny nie wystarczy, więc odpowiedzią jest $2$.