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

Игровое поле является матрицей $$$10^9 \times 10^9$$$, клетка на пересечении $$$a$$$-й строки и $$$b$$$-го столбца обозначается как ($$$a, b$$$).

На игровом поле расположены $$$n$$$ монстров, $$$i$$$-й в клетке ($$$x_i, y_i$$$), остальные клетки пустые. В одной клетке не может находиться более одного монстра.

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

После этого вы должны выбрать один прямоугольник на поле, все монстры внутри выбранного прямоугольника будут уничтожены. За каждую клетку выбранного прямоугольника вы должны заплатить $$$1$$$ монету.

Ваша задача — найти минимальное количество монет, необходимое, чтобы уничтожить всех монстров.

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

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

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

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

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

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

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

Пример
Входные данные
7
3
1 1
1 2
2 1
5
1 1
2 6
6 4
3 3
8 2
4
1 1
1 1000000000
1000000000 1
1000000000 1000000000
1
1 1
5
1 2
4 2
4 3
3 1
3 2
3
1 1
2 5
2 2
4
4 3
3 1
4 4
1 2
Выходные данные
3
32
1000000000000000000
1
6
4
8
Примечание

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

Необходимое перемещение для первого примера.
Необходимое перемещение для пятого примера.