如果存在至少一个满足 $$$l_1 \le x \le r_1$$$ 和 $$$l_2 \le x \le r_2$$$ 的 $$$x$$$,则两条线段 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 相交。
如果 $$$k$$$ 是偶数,则段数组 $$$[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$$$ 被称为美丽的,并且可以通过以下方式将该数组的元素拆分为 $$$\frac{k}{2}$$$ 对:
- 数组的每个元素都属于其中一对;
- 每对中的线段彼此相交;
- 不同对中的线段不相交。
例如,数组 $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$ 很漂亮,因为可以按如下方式形成 $$$3$$$ 对:
- 数组的第一个元素(段 $$$[2, 4]$$$)和数组的第三个元素(段 $$$[2, 4]$$$);
- 数组的第二个元素(段 $$$[9, 12]$$$)和数组的第五个元素(段 $$$[10, 13]$$$);
- 数组的第四个元素(段 $$$[7, 7]$$$)和数组的第六个元素(段 $$$[6, 8]$$$)。
正如您所看到的,每对中的线段相交,并且不同对中的线段没有相交。
给你一个 $$$n$$$ 段 $$$[[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]$$$ 的数组。您必须从该数组中删除尽可能少的元素,以便生成的数组很漂亮。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$) — 数组中的段数。然后是 $$$n$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) 表示第 $$$i$$$ 段。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,打印一个整数 - 必须删除的最小元素数,以便生成的数组美观。
示例
输入 #1
3 7 2 4 9 12 2 4 7 7 4 8 10 13 6 8 5 2 2 2 8 0 10 1 2 5 6 4 1 1 2 2 3 3 4 4
输出 #1
1 3 4
注意
在示例的第一个测试用例中,删除段数组的第 $$$5$$$ 元素就足够了。然后你就得到了数组 $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$,这很漂亮。
在示例的第二个测试用例中,您可以删除数组的第 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 元素。然后你得到数组$$$[[2, 8], [5, 6]]$$$,这很漂亮。
在示例的第三个测试用例中,您必须删除整个数组。