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

在 $Ox$ 轴上有 $n$ 个线段：$[l_1, r_1]$、$[l_2, r_2]$、…、$[l_n, r_n]$。线段 $[l, r]$ 包含从 $l$ 到 $r$（含端点）的所有点，即所有满足 $l \le x \le r$ 的 $x$。

这些线段可以任意放置——彼此嵌套、重合等。线段也可以退化为单个点，即允许 $l_i = r_i$。

给定线段集合的并集，是指一个线段集合，其覆盖的点集与原集合完全相同。例如：

• 若 $n=3$，线段为 $[3, 6]$、$[100, 100]$、$[5, 8]$，则它们的并集包含 $2$ 个线段：$[3, 8]$ 和 $[100, 100]$；
• 若 $n=5$，线段为 $[1, 2]$、$[2, 3]$、$[4, 5]$、$[4, 6]$、$[6, 6]$，则它们的并集包含 $2$ 个线段：$[1, 3]$ 和 $[4, 6]$。

显然，并集中的线段两两互不相交（即无公共内点，但端点可重合）。

你的任务是：恰好删除给定的 $n$ 个线段中的一个，使得剩余 $n-1$ 个线段的并集所含线段数量尽可能多。

例如，若 $n=4$，线段为 $[1, 4]$、$[2, 3]$、$[3, 6]$、$[5, 7]$，则：

• 删除第一个线段后，剩下 $[2, 3]$、$[3, 6]$、$[5, 7]$，其并集含 $1$ 个线段；
• 删除第二个线段后，剩下 $[1, 4]$、$[3, 6]$、$[5, 7]$，其并集含 $1$ 个线段；
• 删除第三个线段后，剩下 $[1, 4]$、$[2, 3]$、$[5, 7]$，其并集含 $2$ 个线段；
• 删除第四个线段后，剩下 $[1, 4]$、$[2, 3]$、$[3, 6]$，其并集含 $1$ 个线段。

因此，应删除第三个线段，得到最大答案 $2$。

请编写程序，在删除任意一个给定线段后，求出剩余 $n-1$ 个线段的并集所能达到的最大线段数量。

注意：若给定集合中存在多个相同的线段，你仍只能删除其中一个。因此删除后的集合一定恰好包含 $n-1$ 个线段。

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试中测试用例的数量。随后是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2\cdot10^5$）——给定集合中线段的数量。接下来是 $n$ 行，每行描述一条线段：一对整数 $l_i$、$r_i$（$-10^9 \le l_i \le r_i \le 10^9$），其中 $l_i$ 和 $r_i$ 分别为第 $i$ 条线段左右端点的坐标。

这些线段以任意顺序给出。

保证所有测试用例的 $n$ 值之和不超过 $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.

输出 $t$ 个整数——按输入顺序给出的 $t$ 个测试用例的答案。答案为：在给定的 $n$ 个线段中删除任意一个后，剩余 $n-1$ 个线段的并集所能形成的最大线段数量。