Watering Plants (Large)

Your greenhouse holds several plants that need water. Each plant takes up an area which is a circle, and no two plants overlap or touch.

You are going to buy two sprinklers. Each sprinkler sprays water on every point 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 at least one of the two circles the sprinklers water.

The sprinklers are installed on the ceiling, so a sprinkler's position may be inside the area of a plant.

Given the center and the radius of every plant, find the minimum radius $R$ for which the two sprinklers can be placed so that every plant gets enough water.

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

Each test case has the following form.

• One line with the number of plants $N$.
• $N$ lines, one per plant, each with three integers X Y R, where $(X, Y)$ is the center of the plant and $R$ is its radius.

Limits

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

For each test case, print one line of the form Case #x: R, where $x$ is the number of the test case starting from 1 and $R$ is the minimum radius of the sprinklers. Print $R$ rounded to exactly four digits after the decimal point.

Every answer in the test data is at least $10^{-5}$ away from a rounding boundary. A solution whose error is at most $10^{-6}$ prints the same digits.

In the first test case of the sample, a sprinkler of radius at least 7 centered at $(20, 15)$ waters the first two plants, and a sprinkler of radius 3 waters the plant at $(40, 10)$.

In the second test case, one of the two sprinklers needs a radius of at least 8. The plant at $(30, 10)$ must also lie completely inside one of the two circles.