В Закулисье обитают натюрморты (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$$$.
Для каждого набора данных выведите одно целое число — минимальное суммарное число шагов, необходимое, чтобы все натюрморты оказались в желаемых точках.
521 55 11-2 321 65 230 40 16 42-1234 5678-1234 5678
052713824
