$$$Ox$$$ 轴 $$$[l_1, r_1]$$$、$$$[l_2, r_2]$$$、...、$$$[l_n, r_n]$$$ 上有 $$$n$$$ 段。线段 $$$[l, r]$$$ 涵盖了从 $$$l$$$ 到 $$$r$$$ 的所有点,因此所有 $$$x$$$ 都满足 $$$l \le x \le r$$$。
段可以任意放置 - 彼此内部、重合等等。线段可以退化为点,即 $$$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$$$ 段,该程序将找到 $$$n-1$$$ 段的并集中的最大段数。
请注意,如果给定集中有多个相等的段,那么您无论如何都只能删除其中一个。因此擦除后的集合将恰好具有 $$$n-1$$$ 段。
输入
第一行包含一个整数 $$$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$$$。
输出
打印 $$$t$$$ 整数 — 按输入顺序给出给定测试用例 $$$t$$$ 的答案。如果删除任何给定的 $$$n$$$ 段,答案是 $$$n-1$$$ 段的并集中的最大段数。
示例
输入 #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