310487: CF1841D. Pairs of Segments

D. Pairs of Segmentstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

For each test case, print one integer — the minimum number of elements you have to remove so that the resulting array is beautiful.

ExampleInput

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

Output

1
3
4

Note

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.

题目大意：给定一个线段数组，判断是否可以通过删除最少数量的线段，使得剩余的线段可以两两配对，且每对线段相交，不同对的线段不相交。

输入数据格式：第一行包含一个整数 t，表示测试用例的数量。每个测试用例的第一行包含一个整数 n，表示线段的数量。接下来 n 行，每行包含两个整数 l_i 和 r_i，表示一个线段的左端点和右端点。

输出数据格式：对于每个测试用例，输出一个整数，表示需要删除的最少线段数量。题目大意：给定一个线段数组，判断是否可以通过删除最少数量的线段，使得剩余的线段可以两两配对，且每对线段相交，不同对的线段不相交。 输入数据格式：第一行包含一个整数 t，表示测试用例的数量。每个测试用例的第一行包含一个整数 n，表示线段的数量。接下来 n 行，每行包含两个整数 l_i 和 r_i，表示一个线段的左端点和右端点。 输出数据格式：对于每个测试用例，输出一个整数，表示需要删除的最少线段数量。