CF2114D Come a Little Closer

游戏场地是一个大小为 $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$ 个怪物的最小成本。

以下是最佳移动的示例，其中要选择的矩形单元格以绿色突出显示。  第一个示例所需的移动。  第五个示例所需的移动。