VegiCat er með $n$ lokuð heiltölubil $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Hann vill búa til runu $a_1, a_2, \ldots, a_n$ með því að velja heiltölu $a_i$ úr hverju bili $[l_i, r_i]$. Það er, $l_i \le a_i \le r_i$ fyrir hvert $1 \le i \le n$.

Staða $i$ kallast metstaða ef $a_i > a_j$ fyrir hvert $1 \le j < i$. Sér í lagi er staða $1$ alltaf metstaða.

Hjálpaðu VegiCat að lágmarka fjölda metstaða. Prentaðu þennan lágmarksfjölda.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur heiltölu $n$ ($1 \le n \le 10^6$), fjölda bila.

$i$-ta línan af næstu $n$ línum inniheldur tvær heiltölur $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), sem lýsa bilinu sem er í boði í stöðu $i$.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta heiltölu — minnsta mögulega fjölda metstaða.

Dæmi

Inntak 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

Úttak 1

2
4

Athugasemd

Í fyrsta prófunartilvikinu er ein besta runan $a = [1, 100, 20, 30]$. Metstöður hennar eru $1$ og $2$.

Í öðru prófunartilvikinu er ein besta runan $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Metstöður hennar eru $1, 2, 5$ og $7$. Staða $8$ er ekki met vegna þess að gildi hennar er jafnt hæsta gildi sem sést hefur hingað til.