D. Пары отрезков
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два отрезка $$$[l_1, r_1]$$$ и $$$[l_2, r_2]$$$ пересекаются, если существует хотя бы одно число $$$x$$$, такое, что $$$l_1 \le x \le r_1$$$ и $$$l_2 \le x \le r_2$$$.

Массив отрезков $$$[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$$$ называется красивым, если $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество элементов, которые нужно удалить, чтобы получившийся массив был красивым.

Пример
Входные данные
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
3
4
Примечание

В первом наборе входных данных достаточно удалить $$$5$$$-й элемент массива отрезков. Тогда получится массив $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$, который является красивым.

Во втором наборе входных данных можно удалить $$$1$$$-й, $$$3$$$-й и $$$4$$$-й элементы массива. Тогда получится массив $$$[[2, 8], [5, 6]]$$$, который является красивым.

В третьем наборе входных данных необходимо удалить весь массив.