VegiCat memiliki $n$ interval bilangan bulat tertutup $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Ia ingin membentuk sebuah barisan $a_1, a_2, \ldots, a_n$ dengan memilih sebuah bilangan bulat $a_i$ dari setiap interval $[l_i, r_i]$. Artinya, $l_i \le a_i \le r_i$ untuk setiap $1 \le i \le n$.

Sebuah posisi $i$ disebut posisi rekor jika $a_i > a_j$ untuk setiap $1 \le j < i$. Secara khusus, posisi $1$ selalu merupakan posisi rekor.

Bantulah VegiCat meminimalkan banyaknya posisi rekor. Keluarkan jumlah minimum ini.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), banyaknya interval.

Baris ke-$i$ dari $n$ baris berikutnya berisi dua bilangan bulat $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), yang mendeskripsikan interval yang tersedia pada posisi $i$.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — banyaknya posisi rekor minimum yang mungkin.

Contoh

Masukan 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

Keluaran 1

2
4

Catatan

Pada kasus uji pertama, salah satu barisan optimal adalah $a = [1, 100, 20, 30]$. Posisi rekornya adalah $1$ dan $2$.

Pada kasus uji kedua, salah satu barisan optimal adalah $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Posisi rekornya adalah $1, 2, 5$, dan $7$. Posisi $8$ bukan merupakan rekor karena nilainya sama dengan nilai maksimum yang pernah muncul sejauh itu.