VegiCat ha $n$ intervalli interi chiusi $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Vuole costruire una sequenza $a_1, a_2, \ldots, a_n$ scegliendo un intero $a_i$ da ciascun intervallo $[l_i, r_i]$. Cioè, $l_i \le a_i \le r_i$ per ogni $1 \le i \le n$.

Una posizione $i$ è chiamata posizione di record se $a_i > a_j$ per ogni $1 \le j < i$. In particolare, la posizione $1$ è sempre una posizione di record.

Aiuta VegiCat a minimizzare il numero di posizioni di record. Stampa questo numero minimo.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ciascun caso di test contiene un intero $n$ ($1 \le n \le 10^6$), il numero di intervalli.

La $i$-esima delle successive $n$ righe contiene due interi $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), che descrivono l'intervallo disponibile nella posizione $i$.

È garantito che la somma di $n$ su tutti i casi di test non supera $10^6$.

Output

Per ciascun caso di test, stampa un intero — il minimo numero possibile di posizioni di record.

Esempi

Input 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

Output 1

2
4

Nota

Nel primo caso di test, una sequenza ottima è $a = [1, 100, 20, 30]$. Le sue posizioni di record sono $1$ e $2$.

Nel secondo caso di test, una sequenza ottima è $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Le sue posizioni di record sono $1, 2, 5$ e $7$. La posizione $8$ non è un record perché il suo valore è uguale al massimo visto finora.