Pylon Link
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

星灵(Protoss)有一个非常重要的建筑是水晶塔(Pylon)。

能量场(Energy Field),是一个以水晶塔为圆心,半径为R的圆,R为正整数。所有的能量场的半径都是相同的。

星灵的绝大部分建筑都需要放置在能量场中。在星际争霸2(StarCraftⅡ)中,用折跃门(Warp Gate)折跃单位也需要放置在能量场中。如果水晶塔被破坏,那么能量场将消失,一些不在能量场范围内的建筑就会停止工作。所以水晶塔对于星灵来说,是一个十分重要的建筑。

tokitsukaze建造了n个水晶塔。她能够设定能量场的半径R。她想把每一个能量场都连接起来,使得单位(看成二维平面上的一个点)能从任意一个水晶塔出发,能到达所有的水晶塔,而且始终在能量场的范围内。她把这种状态,称为星灵的Link状态。

能量场连接的定义是:两个能量场相交或者相切。

tokitsukaze想知道,能量场的半径R至少为多少,能使星灵达到Link状态。

再次提醒:R为正整数。

输入描述:

第一行包含一个正整数T(T≤20),表示T组数据。

对于每一组数据:
第一行包含一个正整数n(2≤n≤500),表示有n个水晶塔。
接下来n行,每行两个整数x,y(-10^9≤x,y≤10^9),表示这个水晶塔的坐标为(x,y)。数据保证没有两个水晶塔在同一个坐标。

输出描述:

对于每组数据,输出一个正整数,表示最小的R,能使星灵达到Link状态。
示例1

输入

复制
2
3
-3 0
1 0
3 2
3
-4 2
-4 -3
1 0

输出

复制
2
3