Delete a Segment

题意翻译

给一个数轴上的 $n$ 条线段，第 $i$ 条覆盖了 $[l_i, r_i]$（如果 $l_i = r_i$ 的话就是一个点）。一个线段集的 _并集_ 是一个与原线段集所覆盖点一样的线段集，例如 $n = 5$，$5$ 条线段分别为 $[1,2]$，$[2,3]$，$[4,5]$，$[4,6]$，$[6,6]$，那么它们的 _并集_ 就是 $[1,3]$ 和 $[4,6]$ 两条线段。现在，你要求出 **正好删去一条线段**后，_并集_ 最多包括多少条线段。 如果两条线段重合，你依然只能删去一条。

题目描述

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.

输入输出样例

输入样例 #1

3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4

输出样例 #1

2
1
5