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

Han vill konstruera en talföljd $a_1, a_2, \ldots, a_n$ genom att välja ett heltal $a_i$ från varje intervall $[l_i, r_i]$. Det vill säga $l_i \le a_i \le r_i$ för varje $1 \le i \le n$.

En position $i$ kallas en rekordposition om $a_i > a_j$ för varje $1 \le j < i$. Speciellt är position $1$ alltid en rekordposition.

Hjälp VegiCat att minimera antalet rekordpositioner. Skriv ut detta minsta antal.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 10^6$), antalet intervall.

Den $i$-te av de följande $n$ raderna innehåller två heltal $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), som beskriver intervallet som är tillgängligt på position $i$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut ett heltal — det minsta möjliga antalet rekordpositioner.

Exempel

Indata 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

Förklaring

I det första testfallet är en optimal talföljd $a = [1, 100, 20, 30]$. Dess rekordpositioner är $1$ och $2$.

I det andra testfallet är en optimal talföljd $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Dess rekordpositioner är $1, 2, 5$ och $7$. Position $8$ är inte ett rekord eftersom dess värde är lika med det hittills största värdet.