Two segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect if there exists at least one $$$x$$$ such that $$$l_1 \le x \le r_1$$$ and $$$l_2 \le x \le r_2$$$.
An array of segments $$$[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$$$ is called beautiful if $$$k$$$ is even, and is possible to split the elements of this array into $$$\frac{k}{2}$$$ pairs in such a way that:
For example, the array $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$ is beautiful, since it is possible to form $$$3$$$ pairs as follows:
As you can see, the segments in each pair intersect, and no segments from different pairs intersect.
You are given an array of $$$n$$$ segments $$$[[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]$$$. You have to remove the minimum possible number of elements from this array so that the resulting array is beautiful.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of segments in the array. Then, $$$n$$$ lines follow, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) denoting the $$$i$$$-th segment.
Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.
For each test case, print one integer — the minimum number of elements you have to remove so that the resulting array is beautiful.
372 49 122 47 74 810 136 852 22 80 101 25 641 12 23 34 4
1 3 4
In the first test case of the example, it is enough to delete the $$$5$$$-th element of the array of segments. Then you get the array $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$, which is beautiful.
In the second test case of the example, you can delete the $$$1$$$-st, $$$3$$$-rd and $$$4$$$-th element of the array. Then you get the array $$$[[2, 8], [5, 6]]$$$, which is beautiful.
In the third test case of the example, you have to delete the whole array.
Name |
---|