D. Тезис о жестоком отрезке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ отрезков на числовой прямой. $$$i$$$-й отрезок представлен как $$$[l_i, r_i]$$$. Изначально все отрезки непомечены.

Вы выполняете следующую операцию многократно, пока не останется непомеченных отрезков:

  1. На $$$k$$$-й операции, если осталось как минимум два непомеченных отрезка, выберите любые два непомеченных отрезка $$$[l_i, r_i]$$$ и $$$[l_j, r_j]$$$, пометьте оба, и добавьте новый помеченный отрезок $$$[x_k, y_k]$$$, удовлетворяющий следующим условиям:
    • $$$l_i \leq x_k \leq r_i$$$,
    • $$$l_j \leq y_k \leq r_j$$$,
    • $$$x_k \leq y_k$$$.
  2. Если остался ровно один непомеченный отрезок, пометьте его.

Ваша задача — определить максимальную возможную сумму длин всех помеченных отрезков в конце процесса. Обратите внимание, что длина отрезка $$$([l,r])$$$ равна $$$r-l$$$.

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

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

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

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

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

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

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

Пример
Входные данные
4
2
1 1000000000
1 1000000000
3
1 10
2 15
3 9
5
1 11
2 7
15 20
1 3
11 15
1
1000000000 1000000000
Выходные данные
2999999997
42
59
0
Примечание

В первом наборе входных данных мы выбираем два данных отрезка и создаем новый отрезок $$$[1, 10^9]$$$.

Во втором наборе входных данных мы выбираем отрезки $$$[1, 10]$$$ и $$$[2, 15]$$$ и создаем новый отрезок $$$[1,15]$$$. Теперь $$$[3, 9]$$$ — единственный отрезок, который остался непомеченным, и он будет помечен на следующем шаге.