游戏场是一个大小为 $$$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$$$ 怪物的最低成本。
示例
输入复制
731 11 22 151 12 66 43 38 241 11 10000000001000000000 11000000000 100000000011 151 24 24 33 13 231 12 52 244 33 14 41 2
输出复制
3 32 1000000000000000000 1 6 4 8
注意
下面是最佳移动的示例,其中要选择的矩形单元格以绿色突出显示。
第一个示例所需的移动。
第五个示例所需的移动。