Xoá một đoạn

Cho $n$ đoạn thẳng trên trục số $Ox$: $[l_1,r_1],[l_2,r_2],\dots ,[l_n,r_n]$. Đoạn $[l,r]$ phủ tất cả các điểm thực $x$ thoả mãn $l\le x\le r$.

Các đoạn có thể nằm trong nhau, trùng nhau hoặc cắt nhau tuỳ ý. Một đoạn cũng có thể suy biến thành một điểm khi $l_i=r_i$.

Hợp của một tập đoạn là tập các đoạn rời nhau (không cắt nhau, không chạm nhau) có hợp đúng bằng tập điểm mà tập đoạn gốc phủ. Ví dụ:

• Với $n=3$ và các đoạn $[3,6],[100,100],[5,8]$ thì hợp gồm $2$ đoạn $[3,8]$ và $[100,100]$.
• Với $n=5$ và các đoạn $[1,2],[2,3],[4,5],[4,6],[6,6]$ thì hợp gồm $2$ đoạn $[1,3]$ và $[4,6]$.

Yêu cầu: hãy chọn đúng một đoạn để xoá khỏi tập sao cho số đoạn trong hợp của $n-1$ đoạn còn lại là lớn nhất có thể.

Lưu ý: nếu có nhiều đoạn giống hệt nhau, mỗi lần ta chỉ xoá được một đoạn, vì vậy tập sau khi xoá luôn có đúng $n-1$ đoạn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ:
  • Dòng đầu chứa số nguyên $n$ — số đoạn.
  • $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i,r_i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số đoạn lớn nhất trong hợp của $n-1$ đoạn sau khi xoá đi đúng một đoạn nào đó.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 2·{10}^5$
• $-{10}^9\le l_i\le r_i\le {10}^9$
• Tổng $n$ qua tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ