F. Телепортация в Бэкрумсе
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Закулисье обитают натюрморты (Still Lifes) — странные существа, похожие на людей. Каждый шаг даётся им с трудом, поэтому они стараются ходить как можно меньше. Зато в этом странном месте они умеют телепортироваться, меняясь друг с другом местами.

В одном из коридоров находятся $$$n$$$ натюрмортов. Коридор можно считать числовой прямой. Натюрморт с номером $$$i$$$ находится в точке $$$s_i$$$ и хочет оказаться в точке $$$t_i$$$.

Можно выполнять следующие операции любое количество раз:

  • поменять местами любых двух натюрмортов с помощью телепортации, не делая шагов;
  • передвинуть любого натюрморта на единицу влево или вправо, сделав один шаг.

В одной точке могут находиться несколько натюрмортов. Найдите минимальное суммарное число шагов, необходимое, чтобы каждый натюрморт $$$i$$$ оказался в точке $$$t_i$$$.

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

Первая строка содержит целое число $$$t$$$ — количество наборов данных ($$$1 \le t \le 10^4$$$).

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

Следующие $$$n$$$ строк содержат по два целых числа $$$s_i$$$ и $$$t_i$$$ — начальную и желаемую координаты натюрморта с номером $$$i$$$ ($$$-10^9 \le s_i, t_i \le 10^9$$$).

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

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

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

Пример
Входные данные
5
2
1 5
5 1
1
-2 3
2
1 6
5 2
3
0 4
0 1
6 4
2
-1234 5678
-1234 5678
Выходные данные
0
5
2
7
13824