VegiCat har $n$ lukkede heltallsintervaller $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Han ønsker å konstruere en følgesekvens $a_1, a_2, \ldots, a_n$ ved å velge et heltall $a_i$ fra hvert intervall $[l_i, r_i]$. Det vil si at $l_i \le a_i \le r_i$ for hver $1 \le i \le n$.

En posisjon $i$ kalles en rekordposisjon hvis $a_i > a_j$ for hver $1 \le j < i$. Spesielt er posisjon $1$ alltid en rekordposisjon.

Hjelp VegiCat med å minimere antallet rekordposisjoner. Skriv ut dette minste antallet.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($1 \le n \le 10^6$), antallet intervaller.

Den $i$-te av de neste $n$ linjene inneholder to heltall $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), som beskriver intervallet som er tilgjengelig på posisjon $i$.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut et heltall — det minste mulige antallet rekordposisjoner.

Eksempler

Inndata 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

Utdata 1

2
4

Forklaring

I det første testtilfellet er én optimal sekvens $a = [1, 100, 20, 30]$. Rekordposisjonene dens er $1$ og $2$.

I det andre testtilfellet er én optimal sekvens $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Rekordposisjonene dens er $1, 2, 5$ og $7$. Posisjon $8$ er ikke en rekord fordi verdien er lik den største verdien som er sett så langt.