Polycarp 在街上发现了 $$$n$$$ 路段。索引为 $$$i$$$ 的段由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 描述——分别是段的开头和结尾的坐标。坡旅甲意识到他不需要所有片段,因此他想删除其中一些片段。
Polycarp 认为,一组 $$$k$$$ 线段是好的,如果该组中有一个线段 $$$[l_i, r_i]$$$ ($$$1 \leq i \leq k$$$),这样它与该组中的每个线段相交(交集必须是一个点或线段)。例如,一组 $$$3$$$ 线段 $$$[[1, 4], [2, 3], [3, 6]]$$$ 就很好,因为线段 $$$[2, 3]$$$ 与该组中的每个线段相交。 $$$4$$$ 段集 $$$[[1, 2], [2, 3], [3, 5], [4, 5]]$$$ 不好。
Polycarp 想知道,为了使剩余的片段形成一个好的集合,他必须删除的最少片段数是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 段数。接下来是描述段的 $$$n$$$ 行。
每个段由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 10^9$$$) 描述 - 分别是段的开头和结尾的坐标。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 需要删除的最小段数,以使剩余段集变得良好。
示例
输入 #1
4 3 1 4 2 3 3 6 4 1 2 2 3 3 5 4 5 5 1 2 3 8 4 5 6 7 9 10 5 1 5 2 4 3 5 3 8 4 8
输出 #1
0 1 2 0