F. Клад из отрезков
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп нашёл на улице $$$n$$$ отрезков. Отрезок с номером $$$i$$$ характеризуется двумя целыми числами $$$l_i$$$ и $$$r_i$$$ — координаты начала и конца отрезка, соответственно. Поликарп понял, что ему нужны не все отрезки, поэтому он хочет удалить некоторые из них.

Поликарп считает, что набор из $$$k$$$ отрезков хороший, если существует отрезок $$$[l_i, r_i]$$$ ($$$1 \leq i \leq k$$$) из набора, такой что он пересекает каждый отрезок из набора (пересечение должно быть точкой или отрезком). Например, набор из $$$3$$$ отрезков $$$[[1, 4], [2, 3], [3, 6]]$$$ является хорошим, так как отрезок $$$[2, 3]$$$ пересекает каждый отрезок из набора. Набор из $$$4$$$ отрезков $$$[[1, 2], [2, 3], [3, 5], [4, 5]]$$$ хорошим не является.

Поликарпу интересно, какое минимальное количество отрезков ему надо удалить, чтобы набор из оставшихся отрезков стал хорошим?

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

В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных даннных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество отрезков в наборе. Далее следуют $$$n$$$ строк с описанием отрезков.

Каждый отрезок описывается двумя целыми числами $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq 10^9$$$) — координаты начала и конца отрезка, соответственно.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
3
1 4
2 3
3 6
4
1 2
2 3
3 5
4 5
5
1 2
3 8
4 5
6 7
9 10
5
1 5
2 4
3 5
3 8
4 8
Выходные данные
0
1
2
0