A13263 | Delete a Segment

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, 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.

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$ .

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.