题目描述

地图生成是制图学中的一项艰巨任务，其中的关键环节是城市标签的自动标注：需要为地图上的每个城市在其位置附加文字标签，且确保任意两个标签互不重叠。本题将处理一个简化的自动地图标注问题。

模型设定：

• 每个城市视为平面直角坐标系中的一个点
• 城市标签是以$xy$轴为基准的正方形文本区域
• 标签位置需满足以下条件：
  1. 城市点必须位于标签上边或下边的中点上
  2. 所有标签尺寸相同
  3. 标签之间不允许重叠（允许边线重合）

图1展示了一个合格标注的示例（标签文字未显示）。

输入要求： 给定所有城市点的整数坐标，求能满足良好标注条件的最大标签尺寸（整数值）。

输入格式

• 首行为测试用例数$t$（$1 \leq t \leq 10$）
• 每个测试用例包含：
  • 城市数量$m$（$3 \leq m \leq 100$）
  • 后续$m$行，每行给出城市坐标$(X,Y)$（$-10000 \leq X,Y \leq 10000$）
  • 所有城市坐标唯一

输出格式

每个测试用例输出一行，给出该地图能实现良好标注的最大标签尺寸（整数）

输入样例

1
6
1 1
2 3
3 2
4 4
10 4
2 5

输出样例

2

题目来源

Tehran 2003