The Lebesgue number, which emerged in the Lebesgue's number lemma, is an important concept in topology of metric space and mathematical analysis.

Consider the case when the metric space is R^{2}.
The Lebesgue's number lemma says if F a closed set,
and {E_{i}} an open cover of F(that is a class of sets whose union contains F),
then there exist a positive real number L, such that for every point p in F,
exist an open set E_{i} in the cover
which contains the open L-neibourhood of p.
We call this number a Lebesgue number with respect to closed set F
and the open cover {E_{i}}.

In this problem, we use the Manhattan distance d on R^{2},
that is for p(x_{1}, y_{1}) and q(x_{2}, y_{2}),
d(p, q) = |x_{1} - x_{2}| + |y_{1} - y_{2}|.

Then for a point p and positive a real number e,
the open e-neibourhood of p, denoted by O(p, e), is the set {q | d(p, q) < e};
while the closed e-neibourhood of p, denoted by C(p, e), is the set {q | d(p, q) <= e}.

We also assume the open cover is finite. More over,
the closed set F is a closed neibourhood of some point;
and each open set is an open neibourhood of some point.

That is, for a point p_{0} and a positive real number e_{0},
a finite open cover of the closed e_{0}-neibourhood of p_{0},
namely C(p_{0}, e_{0}), is a sequence of n open neibourhoods,
O(p_{i}, e_{i}) (i=1,...,n), such that
C(p_{0}, e_{0}) is contained in the union of
O(p_{i}, e_{i}) (i=1,...,n).

Here comes the problem, given a point p_{0}(x_{0}, y_{0}),
a positive real number e_{0},
and a finite open cover of C(p_{0}, e_{0}),
that is O(p_{i}, e_{i}) (i=1,...,n).
Your task is to calculate

*sup*{L | L is a Lebesgue number with
respect to C(p_{0}, e_{0}) and O(p_{i}, e_{i}) (i=1,...,n)}
^{note1}.

Number of test cases T(1 <= T <= 30) on the first line.
Then T cases follows. Each case begins with an integer n(1<=n<=1000),
and then n + 1 lines follows, the i-th(starts from 0) line contains 3 real numbers
x_{i}, y_{i}, e_{i},
(|x_{i}|, |y_{i}| < 1000, 0 < e < 1000).
You can assume O(p_{i}, e_{i}) (i=1,...,n) is an open cover of
C(p_{0}, e_{0}).

For each test case, output one line with a single real number L,

*sup*{L | L is a Lebesgue number with respect to
C(p_{0}, e_{0}) and O(p_{i}, e_{i}) (i=1,...,n)}.

Use `printf("%.3f\n", L);`

to output the answer.

5 1 0 0 1 1 0 3 1 0 0 1 0 0 2 4 0 0 2 0 1 2 1 0 2 -1 0 2 0 -1 2 4 0 0 2 0 1 3 1 0 3 -1 0 3 0 -1 3 4 2 2 2 2 4 3 4 2 3 0 2 3 2 0 3

1.000 1.000 1.000 2.000 1.000

Note 1

Remember in mathematical analysis, the superieur of a non-empty subset A of real numbers,
*sup*A is the lowest upper bound of A.

cauchy

Sichuan University Programming Contest 2011 Final