Description

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 R2. The Lebesgue's number lemma says if F a closed set, and {Ei} 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 Ei 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 {Ei}.

In this problem, we use the Manhattan distance d on R2, that is for p(x1, y1) and q(x2, y2), d(p, q) = |x1 - x2| + |y1 - y2|.
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 p0 and a positive real number e0, a finite open cover of the closed e0-neibourhood of p0, namely C(p0, e0), is a sequence of n open neibourhoods, O(pi, ei) (i=1,...,n), such that C(p0, e0) is contained in the union of O(pi, ei) (i=1,...,n).

Here comes the problem, given a point p0(x0, y0), a positive real number e0, and a finite open cover of C(p0, e0), that is O(pi, ei) (i=1,...,n). Your task is to calculate
sup{L | L is a Lebesgue number with respect to C(p0, e0) and O(pi, ei) (i=1,...,n)} note1.

Input

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 xi, yi, ei, (|xi|, |yi| < 1000, 0 < e < 1000). You can assume O(pi, ei) (i=1,...,n) is an open cover of C(p0, e0).

Output

For each test case, output one line with a single real number L,
sup{L | L is a Lebesgue number with respect to C(p0, e0) and O(pi, ei) (i=1,...,n)}.
Use printf("%.3f\n", L); to output the answer.

Sample Input

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

Sample Output

1.000
1.000
1.000
2.000
1.000

Hint

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

Author

cauchy

Source

Sichuan University Programming Contest 2011 Final