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$）—— 怪物所在格子的坐标。所有 $(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

样例解释

• 第一个样例的最优移动方式及选中的矩形（绿色高亮）见题面图示。
• 第五个样例的最优移动方式及选中的矩形（绿色高亮）见题面图示。