The Institute of Circles with Perimetral Connections (ICPC) has recently discovered that
several machines that were working in their diverse productive areas were totally obsolete.
Of course, all machines in the Institute contain several circles.
The Supreme Chief Director Manager President of the ICPC asked their Computer Aided
Problem Solving department to help in overcoming this situation. They have signaled
you as the maximum responsible, so you better get to work.
Many machines in the Institute have mechanical parts in the shape of a circle that need
to be rotated clockwise in order for the machine to work. Currently, each circular part
is connected to a different electrical engine that does the job. You noted, however, that
when many circles are coplanar, you can connect them with elastic bands and they will
rotate all together with the energy of one engine.
This marvelous idea lead you to a new problem. What’s the optimal way to connect
all the circles? In general, there are many ways to place elastic bands and make all the
circles be connected. Since some of the rotating power of the system is lost in the tension
of the elastic bands, you want to minimize the total length of elastic bands used.
Formally, the length of the elastic band that connects two cricles is the perimeter of the
smallest convex area that contains both circles. The total length is the sum of the lengths
of all used elastic bands. Two circles can be connected with an elastic band even if the
band touches or goes through any number of other circles or elastic bands.

Input

The input contains several test cases, each one described in several lines. The first line
contains an integer N indicating the number of circles to connect (2 ≤ N ≤ 3000). Each
of the next N lines describes a different circle using three integers X, Y and R separated
by single spaces (1 ≤ X, Y, R ≤ 10⁶ ). The values X and Y represent the coordinates of
the center of the circle in the XY plane, while the value R indicates its radius. You may
assume that within each test case no two circles overlap or touch each other. The last
line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line containing a real number representing the minimum
total length of elastic band needed to connect all the circles. Round the result to the
closest rational number with three decimal places. In case of ties, round up. Always use
exactly three digits after the decimal point, even if it means finishing with a zero.

Example

Input:
3
2 2 2
1 6 1
6 1 1
2
1 1 1
1 4 1
-1

Output:
35.829
12.283