SP9260 PERFECTR - Perfect Road

Byteland 是在 SPOJ 上经常提到的一个虚构城市。 有个古老的传说，描述了 Byteland 居民生活在一个简单的小镇上，类似于旧时加州西部，那里只有一条笔直的主干道，大约 500 米长，所有的房屋、酒吧和酒店都面向这条路。不过，在 Byteland，有一个小小的区别，这里的每栋房屋都有自己的小路垂直连接到主干道，法律规定这些小路必须垂直于主干道。 因此，他们的生活空间可以抽象为一个二维网格，其中整数坐标表示。主干道就是 x 轴，房屋则是连接到 x 轴上的点，这些点可以在 y 轴的正负两个方向延伸。 在这个特别的城市里，如果一个居民 A 想拜访另一个居民 B，他需要先沿着自家与主干道连接的道路走到主干道上，再沿着主干道走到对方家连接的小路，然后再进入对方的家。而如果他们的家在同一条垂线上，他们只需沿着直线距离前往对方家即可。 两个人家之间的距离定义如下： 1. 若两个人的家在同一条垂线上（即有相同的 x 坐标），那么他们之间的距离就是他们 y 坐标的绝对差值。 2. 否则，距离为 A 的家到主干道的距离加 B 的家到主干道的距离，再加上他们的 x 坐标的绝对差值。 例如，假设有三个人分别住在 (1,1)、(1,4) 和 (4,1)。  为了让 Byteland 的居民生活更加便利，政府计划采取一个大胆的措施：通过将主干道移动到 $y = N$ 的水平线上（其中 $N$ 为整数），从而最小化任意两个人家之间的最大距离。若主干道已在最优位置，则不作调整。 你的任务是，给定房屋的 x 和 y 坐标，计算在主干道调整到最优位置后，任意两个人家之间的最大距离。

第一行为测试用例的数量 $T$（$3 \le T \le 10^5$）。接下来的 $T$ 组测试数据中： 每组测试数据的第一行为一个整数 $N$（$2 \le N \le 10^5$），表示房屋的数量。 接下来的 $N$ 行中，每一行包含两个用空格分开的整数，分别代表一个 Byteland 房屋的 x 和 y 坐标。

对于每个测试用例，输出一行，表示经过调整后任意两个人家之间的最大距离。

- $3 \le T \le 10^5$ - $2 \le N \le 10^5$ - $0 \le |x|, |y| \le 10^9$ **本翻译由 AI 自动生成**