C. Средняя конструкция
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$a_1, a_2, \ldots, a_m$$$ изначально заполнен нулями. Вам даны $$$n$$$ попарно различных отрезков $$$1 \le l_i \le r_i \le m$$$. Вы должны выбрать произвольное подмножество этих отрезков (в частности, можно выбрать пустое множество). После этого происходит следующее:

  • Для каждого $$$i = 1, 2, \ldots, n$$$, если отрезок $$$(l_i, r_i)$$$ выбран в подмножество, то для каждого индекса $$$l_i \le j \le r_i$$$ вы увеличиваете $$$a_j$$$ на $$$1$$$ (то есть $$$a_j$$$ заменяете на $$$a_j + 1$$$). Если отрезок $$$(l_i, r_i)$$$ не выбран, массив не изменяется.
  • После этого (после обработки всех значений $$$i = 1, 2, \ldots, n$$$) вы считаете $$$\max(a)$$$ как максимальное значение среди всех элементов $$$a$$$. Аналогично, $$$\min(a)$$$ считается как минимальное значение.
  • Наконец, стоимость выбранного подмножества отрезков объявляется равной $$$\max(a) - \min(a)$$$.

Найдите наибольшую стоимость по всем подмножествам данного множества отрезков.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — количество отрезков и длина массива.

Следующие $$$n$$$ строк каждого набора входных данных описывают отрезки: $$$i$$$-я из них содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$). Гарантируется, что все отрезки попарно различны.

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

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

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

Пример
Входные данные
6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789
Выходные данные
1
3
2
3
4
4
Примечание

В первом наборе входных данных доступен всего один отрезок. Если его не выбирать, то массив будет равен $$$a = [0, 0, 0]$$$, стоимость такого (пустого) подмножества отрезков равна $$$0$$$. Если же выбрать единственный доступный отрезок, то массив станет равен $$$a = [0, 1, 0]$$$, и стоимость будет равна $$$1 - 0 = 1$$$.

Во втором наборе входных данных можно выбрать все отрезки: массив в таком случае будет равен $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$. Стоимость будет равна $$$3 - 0 = 3$$$.