1285E · Delete a Segment

Problem: There are $n$ segments on a $Ox$ axis $[l_1, r_1]$, $[l_2, r_2]$, ..., $[l_n, r_n]$. Segment $[l, r]$ covers all points from $l$ to $r$ inclusive, so all $x$ such that $l \le x \le r$.

Segments can be placed arbitrarily  — be inside each other, coincide and so on. Segments can degenerate into points, that is $l_i=r_i$ is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:

• if $n=3$ and there are segments $[3, 6]$, $[100, 100]$, $[5, 8]$ then their union is $2$ segments: $[3, 8]$ and $[100, 100]$;
• if $n=5$ and there are segments $[1, 2]$, $[2, 3]$, $[4, 5]$, $[4, 6]$, $[6, 6]$ then their union is $2$ segments: $[1, 3]$ and $[4, 6]$.

Obviously, a union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given $n$ so that the number of segments in the union of the rest $n-1$ segments is maximum possible.

For example, if $n=4$ and there are segments $[1, 4]$, $[2, 3]$, $[3, 6]$, $[5, 7]$, then:

• erasing the first segment will lead to $[2, 3]$, $[3, 6]$, $[5, 7]$ remaining, which have $1$ segment in their union;
• erasing the second segment will lead to $[1, 4]$, $[3, 6]$, $[5, 7]$ remaining, which have $1$ segment in their union;
• erasing the third segment will lead to $[1, 4]$, $[2, 3]$, $[5, 7]$ remaining, which have $2$ segments in their union;
• erasing the fourth segment will lead to $[1, 4]$, $[2, 3]$, $[3, 6]$ remaining, which have $1$ segment in their union.

Thus, you are required to erase the third segment to get answer $2$.

Write a program that will find the maximum number of segments in the union of $n-1$ segments if you erase any of the given $n$ segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $n-1$ segments.

Input Format: The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then the descriptions of $t$ test cases follow.

The first of each test case contains a single integer $n$ ($2 \le n \le 2\cdot10^5$) — the number of segments in the given set. Then $n$ lines follow, each contains a description of a segment — a pair of integers $l_i$, $r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), where $l_i$ and $r_i$ are the coordinates of the left and right borders of the $i$-th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output Format: Print $t$ integers — the answers to the $t$ given test cases in the order of input. The answer is the maximum number of segments in the union of $n-1$ segments if you erase any of the given $n$ segments.