VegiCat có $n$ đoạn số nguyên đóng $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Anh ấy muốn xây dựng một dãy $a_1, a_2, \ldots, a_n$ bằng cách chọn một số nguyên $a_i$ từ mỗi đoạn $[l_i, r_i]$. Tức là $l_i \le a_i \le r_i$ với mọi $1 \le i \le n$.

Một vị trí $i$ được gọi là vị trí kỷ lục nếu $a_i > a_j$ với mọi $1 \le j < i$. Đặc biệt, vị trí $1$ luôn là một vị trí kỷ lục.

Hãy giúp VegiCat cực tiểu hóa số lượng vị trí kỷ lục. In ra số lượng tối thiểu này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), số lượng bộ test. Mô tả của các bộ test theo sau.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên $n$ ($1 \le n \le 10^6$), số lượng đoạn.

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), mô tả đoạn có thể chọn tại vị trí $i$.

Dữ liệu đảm bảo tổng của $n$ trên tất cả các bộ test không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — số lượng vị trí kỷ lục ít nhất có thể.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2
4

Ghi chú

Trong bộ test đầu tiên, một dãy tối ưu là $a = [1, 100, 20, 30]$. Các vị trí kỷ lục của nó là $1$ và $2$.

Trong bộ test thứ hai, một dãy tối ưu là $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Các vị trí kỷ lục của nó là $1, 2, 5$, và $7$. Vị trí $8$ không phải là kỷ lục vì giá trị của nó bằng giá trị lớn nhất đã xuất hiện trước đó.