VegiCatilla on $n$ suljettua kokonaislukuväliä $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Hän haluaa muodostaa lukujonon $a_1, a_2, \ldots, a_n$ valitsemalla kokonaisluvun $a_i$ jokaiselta väliltä $[l_i, r_i]$. Toisin sanoen $l_i \le a_i \le r_i$ kaikilla $1 \le i \le n$.

Kohtaa $i$ kutsutaan ennätyskohdaksi, jos $a_i > a_j$ kaikilla $1 \le j < i$. Erityisesti kohta $1$ on aina ennätyskohta.

Auta VegiCatia minimoimaan ennätyskohtien lukumäärä. Tulosta tämä pienin mahdollinen lukumäärä.

Syöte

Ensimmäisellä rivillä on kokonaisluku $T$ ($1 \le T \le 10^4$), testitapausten lukumäärä. Seuraavaksi annetaan testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäisellä rivillä on kokonaisluku $n$ ($1 \le n \le 10^6$), välien lukumäärä.

Seuraavista $n$ rivistä $i$:nnellä on kaksi kokonaislukua $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), jotka kuvaavat kohdassa $i$ käytettävissä olevan välin.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle kokonaisluku — pienin mahdollinen ennätyskohtien lukumäärä.

Esimerkit

Syöte 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

Tuloste 1

2
4

Huomautus

Ensimmäisessä testitapauksessa eräs optimaalinen jono on $a = [1, 100, 20, 30]$. Sen ennätyskohdat ovat $1$ ja $2$.

Toisessa testitapauksessa eräs optimaalinen jono on $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Sen ennätyskohdat ovat $1, 2, 5$ ja $7$. Kohta $8$ ei ole ennätys, koska sen arvo on yhtä suuri kuin tähän mennessä nähty suurin arvo.