Watering Plants

Your greenhouse holds several potted plants that need water. The area a plant takes up is a circle, and no two plants overlap or touch each other.

You are going to buy two sprinklers. Each sprinkler waters everything inside a circle of radius $R$.

One sprinkler runs in the morning and the other runs at night. A plant gets enough water only if its whole area is watered in the morning, or its whole area is watered at night. So the circle of each plant must lie completely inside one of the two circles the sprinklers water.

The position and radius of every plant are given. Find the minimum radius $R$ for which the two sprinklers can be placed so that every plant is watered. The sprinklers are installed on the ceiling, so a sprinkler may sit inside the area of a plant.

The first line contains the number of test cases $C$.

Each test case is given as follows.

• The first line contains the number of plants $N$.
• Each of the next $N$ lines contains three integers $X$, $Y$, $R$. $(X, Y)$ is the center of the plant and $R$ is its radius.

Limits

• Every number in the input is an integer.
• $1 \le C \le 10$
• $1 \le N \le 20$
• $1 \le X \le 1000$
• $1 \le Y \le 1000$
• $1 \le R \le 100$
• No two plants overlap or touch each other.

For each test case, print one line of the form Case #x: R, where $x$ is the test case number starting from 1 and $R$ is the minimum sprinkler radius.

Print the radius rounded to six digits after the decimal point. When the minimum radius is 7, print 7.000000.

In the first case of the example, a sprinkler of radius 7 or more centered at (20, 15) waters the first two plants. The plant at (40, 10) is covered by a radius of 3 or more.

In the second case, one of the two sprinklers needs a radius of 8 or more. The plant at (30, 10) also has to be covered completely by one of the two sprinklers.