Nene đang huấn luyện đội bóng rổ của mình với tư cách là một huấn luyện viên. Đội của Nene gồm $n$ cầu thủ, được đánh số từ $1$ đến $n$. Cầu thủ thứ $i$ có khoảng sải tay $[l_i, r_i]$. Hai cầu thủ $i$ và $j$ ($i \neq j$) có thể chuyền bóng cho nhau khi và chỉ khi $|i-j| \in [l_i+l_j, r_i+r_j]$ (ở đây, $|x|$ ký hiệu giá trị tuyệt đối của $x$).

Nene muốn kiểm tra khả năng phối hợp của các cầu thủ này. Để làm điều đó, cô ấy sẽ tổ chức một vài vòng đánh giá.

• Trong mỗi vòng, Nene sẽ chọn một dãy cầu thủ $p_1, p_2, \ldots, p_m$ sao cho cầu thủ $p_i$ và $p_{i+1}$ có thể chuyền bóng cho nhau với mọi $1 \le i < m$. Độ dài của dãy $m$ có thể do Nene tùy chọn. Mỗi cầu thủ có thể xuất hiện trong dãy $p_1, p_2, \ldots, p_m$ nhiều lần hoặc không xuất hiện lần nào.
• Sau đó, Nene sẽ ném bóng cho cầu thủ $p_1$, cầu thủ $p_1$ sẽ chuyền bóng cho cầu thủ $p_2$ và cứ tiếp tục như vậy... Cầu thủ $p_m$ sẽ ném bóng ra khỏi sân bóng rổ để nó không thể được sử dụng nữa.

Với tư cách là huấn luyện viên, Nene muốn mỗi cầu thủ trong số $n$ cầu thủ xuất hiện trong ít nhất một vòng đánh giá. Vì Nene phải đi hẹn hò sau giờ học, cô ấy muốn bạn tính toán số vòng đánh giá tối thiểu cần thiết để hoàn thành nhiệm vụ.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $t$ ($1 \le t \le 2\cdot 10^5$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 2\cdot 10^6$) — số lượng cầu thủ.

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $l_i$ và $r_i$ ($1 \le l_i \le r_i \le n$) — khoảng sải tay của cầu thủ thứ $i$.

Đảm bảo rằng tổng của $n$ trên tất cả các trường hợp thử nghiệm không vượt quá $2\cdot 10^6$.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, hãy in ra một số nguyên — số vòng đánh giá tối thiểu Nene cần để hoàn thành công việc của mình.

Ví dụ

Input 1

5
2
1 1
1 1
2
1 1
2 2
3
1 3
1 3
1 3
5
1 1
2 2
1 5
2 2
1 1
6
1 2
5 5
2 3
2 3
2 2
1 2

Output 1

2
2
2
1
3

Ghi chú

Trong hai trường hợp thử nghiệm đầu tiên, Nene có thể tổ chức hai vòng đánh giá: một vòng với $p=[1]$ và một vòng với $p=[2]$. Có thể chứng minh rằng tổ chức một vòng đánh giá là không đủ, vì vậy câu trả lời là $2$.

Trong trường hợp thử nghiệm thứ ba, Nene có thể tổ chức hai vòng đánh giá: một vòng với $p=[1,3]$ và một vòng với $p=[2]$. Cầu thủ $1$ có thể chuyền bóng cho cầu thủ $3$ vì $|3-1|=2 \in [1+1,3+3]$. Có thể chứng minh rằng tổ chức một vòng đánh giá là không đủ, vì vậy câu trả lời là $2$.