VegiCat ma $n$ domkniętych przedziałów liczb całkowitych $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Chce skonstruować ciąg $a_1, a_2, \ldots, a_n$, wybierając liczbę całkowitą $a_i$ z każdego przedziału $[l_i, r_i]$. Oznacza to, że $l_i \le a_i \le r_i$ dla każdego $1 \le i \le n$.

Pozycję $i$ nazywamy pozycją rekordową, jeśli $a_i > a_j$ dla każdego $1 \le j < i$. W szczególności pozycja $1$ zawsze jest pozycją rekordową.

Pomóż VegiCatowi zminimalizować liczbę pozycji rekordowych. Wypisz tę minimalną liczbę.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą liczbę przedziałów.

$i$-ty z kolejnych $n$ wierszy zawiera dwie liczby całkowite $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), opisujące przedział dostępny na pozycji $i$.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalną możliwą liczbę pozycji rekordowych.

Przykład

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

Wyjście 1

2
4

Uwagi

W pierwszym przypadku testowym jednym z optymalnych ciągów jest $a = [1, 100, 20, 30]$. Jego pozycje rekordowe to $1$ oraz $2$.

W drugim przypadku testowym jednym z optymalnych ciągów jest $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Jego pozycje rekordowe to $1, 2, 5$ oraz $7$. Pozycja $8$ nie jest rekordem, ponieważ jej wartość jest równa dotychczasowemu maksimum.