VegiCat hat $n$ abgeschlossene ganzzahlige Intervalle $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Er möchte eine Folge $a_1, a_2, \ldots, a_n$ konstruieren, indem er aus jedem Intervall $[l_i, r_i]$ eine ganze Zahl $a_i$ auswählt. Das heißt, es gilt $l_i \le a_i \le r_i$ für alle $1 \le i \le n$.

Eine Position $i$ wird Rekordposition genannt, wenn $a_i > a_j$ für alle $1 \le j < i$ gilt. Insbesondere ist Position $1$ immer eine Rekordposition.

Hilf VegiCat, die Anzahl der Rekordpositionen zu minimieren. Gib diese minimale Anzahl aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$), die Anzahl der Intervalle.

Die $i$-te der nächsten $n$ Zeilen enthält zwei ganze Zahlen $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), die das an Position $i$ verfügbare Intervall beschreiben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus — die minimal mögliche Anzahl von Rekordpositionen.

Beispiele

Eingabe 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

Ausgabe 1

2
4

Hinweis

Im ersten Testfall ist eine optimale Folge $a = [1, 100, 20, 30]$. Ihre Rekordpositionen sind $1$ und $2$.

Im zweiten Testfall ist eine optimale Folge $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Ihre Rekordpositionen sind $1, 2, 5$ und $7$. Position $8$ ist kein Rekord, da ihr Wert gleich dem bisher gesehenen Maximum ist.