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

На координатной прямой $$$Ox$$$ заданы $$$n$$$ отрезков $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$. Отрезок $$$[l, r]$$$ покрывает все точки от $$$l$$$ до $$$r$$$ включительно, то есть такие $$$x$$$, что $$$l \le x \le r$$$.

Отрезки могут располагаться произвольным образом  — вкладываться друг в друга, совпадать и т.п. Отрезки могут вырождаться в точку, то есть допустимо, что $$$l_i=r_i$$$.

Объединением набора отрезков называется такой минимальный набор отрезков, который покрывает в точности тот же набор точек, что и заданный набор. Например:

  • если $$$n=3$$$ и отрезки имеют вид $$$[3, 6]$$$, $$$[100, 100]$$$, $$$[5, 8]$$$, то их объединение состоит из $$$2$$$ отрезков: $$$[3, 8]$$$ и $$$[100, 100]$$$;
  • если $$$n=5$$$ и отрезки имеют вид $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[4, 5]$$$, $$$[4, 6]$$$, $$$[6, 6]$$$ то их объединение состоит из $$$2$$$ отрезков: $$$[1, 3]$$$ и $$$[4, 6]$$$.

Очевидно, что объединение — это набор непересекающихся отрезков.

Требуется удалить ровно один отрезок из заданных $$$n$$$ таким образом, чтобы количество отрезков в объединении оставшихся $$$n-1$$$ было наибольшим.

Например, если $$$n=4$$$ и отрезки имеют вид $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, то:

  • если из набора удалить первый отрезок, то останутся отрезки $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, объединение которых состоит из $$$1$$$ отрезка;
  • если из набора удалить второй отрезок, то останутся отрезки $$$[1, 4]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, объединение которых состоит из $$$1$$$ отрезка;
  • если из набора удалить третий отрезок, то останутся отрезки $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[5, 7]$$$, объединение которых состоит из $$$2$$$ отрезков;
  • если из набора удалить четвертый отрезок, то останутся отрезки $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$, объединение которых состоит из $$$1$$$ отрезка.

Таким образом, в примере выше надо обязательно удалять третий отрезок, чтобы получить ответ $$$2$$$.

Напишите программу, которая найдет наибольшее количество отрезков, которые получатся в объединении $$$n-1$$$ оставшегося, если можно удалить любой из заданных $$$n$$$ отрезков.

Обратите внимание, что если в заданном наборе есть несколько одинаковых отрезков, то удалить вы всё-равно можете ровно один из них. То есть набор отрезков после удаления одного будет содержать ровно $$$n-1$$$ отрезок.

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

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

Первая строка каждого набора содержит целое число $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — количество отрезков в заданном наборе. Далее в $$$n$$$ строках заданы сами отрезки парами целых чисел $$$l_i$$$, $$$r_i$$$ ($$$-10^9 \le l_i \le r_i \le 10^9$$$), где $$$l_i$$$ и $$$r_i$$$ — координаты левого и правого конца $$$i$$$-го отрезка, соответственно.

Отрезки заданы в произвольном порядке.

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

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

Выведите $$$t$$$ чисел — ответы на заданные $$$t$$$ наборов входных данных в порядке их следования в тесте. Ответ равен максимальному количеству отрезков в объединении $$$n-1$$$ отрезка из $$$n$$$ заданных, если допускается удалить один любой отрезок.

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