A16026 | Pairs of Segments

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:

- every element of the array belongs to exactly one of the pairs;
- segments in each pair intersect with each other;
- segments in different pairs do not intersect.

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:

- the first element of the array (segment $[2, 4]$ ) and the third element of the array (segment $[2, 4]$ );
- the second element of the array (segment $[9, 12]$ ) and the fifth element of the array (segment $[10, 13]$ );
- the fourth element of the array (segment $[7, 7]$ ) and the sixth element of the array (segment $[6, 8]$ ).

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.