G2. Уничтожение Вселенной (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии $$$n \leq 10^6$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Орангутаны — могущественные существа — настолько могущественные, что им нужна всего $$$1$$$ единица времени, чтобы уничтожить все уязвимые планеты во Вселенной!

Во Вселенной существует $$$n$$$ планет. Каждая планета имеет интервал уязвимости $$$[l, r]$$$, в течение которого она будет подвержена разрушению орангутанами. Орангутаны также могут расширять интервал уязвимости любой планеты на $$$1$$$ единицу.

В частности, предположим, что расширение происходит на планете $$$p$$$ с интервалом уязвимости $$$[l_p, r_p]$$$. Тогда результирующий интервал уязвимости может быть либо $$$[l_p - 1, r_p]$$$, либо $$$[l_p, r_p + 1]$$$.

При заданном множестве планет орангутаны могут уничтожить все планеты, если интервалы уязвимости всех планет из множества пересекаются хотя бы в одной общей точке. Назовём счётом такого набора минимальное количество расширений, которое необходимо выполнить.

Орангутанов интересует сумма счётов всех непустых подмножеств планет во Вселенной. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — количество планет во Вселенной.

Следующие $$$n$$$ строк содержат по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — начальный интервал уязвимости $$$i$$$-й планеты.

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

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

Для каждого набора входных данных выведите целое число — сумму счётов всех непустых подмножеств планет во Вселенной, по модулю $$$998\,244\,353$$$.

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

В первом наборе входных данных есть семь непустых подмножеств планет, которые мы должны рассмотреть:

  • Для каждого из подмножеств $$$\{[1,1]\}, \{[2,3]\}, \{[3,3]\}$$$, оценка равна $$$0$$$.
  • Для подмножества $$$\{[2,3], [3,3]\}$$$ оценка равна $$$0$$$, потому что точка $$$3$$$ уже содержится в интервале уязвимости обеих планет.
  • Для подмножества $$$\{[1,1], [2,3]\}$$$ оценка равна $$$1$$$. Используя одну операцию по изменению интервала уязвимости второй планеты на $$$[1,3]$$$, обе планеты теперь имеют точку $$$1$$$ в своем интервале.
  • Для подмножества $$$\{[1,1], [3,3]\}$$$ оценка равна $$$2$$$. С помощью двух операций по изменению интервала уязвимости первой планеты на $$$[1,3]$$$, обе планеты теперь имеют точку $$$3$$$ в своем интервале.
  • Для подмножества $$$\{[1,1], [2,3], [3,3]\}$$$ оценка равна $$$2$$$. С помощью одной операции по изменению интервала уязвимости первой планеты на $$$[1,2]$$$ и одной операции по изменению интервала уязвимости третьей планеты на $$$[2,3]$$$, все три планеты будут иметь точку $$$2$$$ в своем интервале.

Сумма оценок всех непустых подмножеств первого набора входных данных равна $$$0 \cdot 4 + 1 \cdot 1 + 2\cdot2 = 5$$$.