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 signalled 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 marvellous 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 circles 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 centre 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