Problem: A crop circle suddenly appeared on the vast agricultural land of Argentina. A total of n crop circles were confirmed, including overlapping, popping, large, and small ones.

When a mystery hunter tried to capture the whole picture of a crop circle from the air, he found it difficult to show the beautiful pattern in the image because the outline of each circle was not clear.

Therefore, the mystery hunter proposed to emphasize the contour by installing a string of special material along the contour.

The part where the string is installed is the part on the circumference of one crop circle that is not included in any other crop circle.

The film crew asked you to create a program to measure the required string length. Enter the center coordinates and radius of each crop circle and create a program to report the length of the string to be installed.

For reference, the first and second cases of the input / output examples are shown in FIGS. 1 and 2, respectively. The part of the string is shown by a thick line.


<image>


Figure 1



<image>


Figure 2



Constraints

* n ≤ 100
* -1000 ≤ xi, yi ≤ 1000
* 0 <ri ≤ 100

Input

Multiple datasets are given as input. Each dataset is given in the following format:

n (number of crop circles: integer)
x1 y1 r1 (center coordinates and radius of the first circle: real numbers separated by blanks)
x2 y2 r2 (center coordinates and radius of the second circle: real numbers separated by blanks)
..
..
xn yn rn (center coordinates and radius of the nth circle: real numbers separated by blanks)


When n is 0, it indicates the end of input.

Output

Output the string length on one line for each dataset. The output may contain an error of 0.000001 or less.

Example

Input

4
6 4 2
4 7 3
7 10 3
13 6 1
4
7 4 2
4 7 3
7 10 3
11 6 3
0


Output

39.664699289572
45.627024663706

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<complex>
#include<vector>
#include<algorithm>

#define EPS 1.0e-12
#define PI acos(-1.0)

using namespace std;

typedef double elem;
typedef complex<elem> point, vec;

inline elem sq(elem a){ return a * a; }
inline elem dist(const point &p1, const point &p2){ return abs(p2-p1); }
inline bool eq(elem a, elem b){ return abs(a-b)<EPS; }
inline bool eqv(const vec &a, const vec &b){ return eq( a.real(), b.real() ) && eq( a.imag(), b.imag() );  }
inline elem dot(const vec &a, const vec &b){ return a.real() * b.real() + a.imag() * b.imag(); } 
inline elem cross(const vec &a, const vec &b){ return a.real() * b.imag() - a.imag() * b.real(); }
inline elem rad(const vec &a, const vec &b){ return acos( dot(a,b) / ( abs(a) * abs(b) ) ); }
inline vec uvec(const vec &a){ return a / abs(a); }
inline vec normr(const vec &a){ return a * vec(0,-1); }
inline vec norml(const vec &a){ return a * vec(0,1); }
inline vec unormr(const vec &a){ return uvec( normr( a ) ); }
inline vec unorml(const vec &a){ return uvec( norml( a ) ); }

struct circle{
	elem r; point c;
	elem Perimeter()const{ return 2 * r * PI; }
	bool Inside(const point &p)const{ return dist(p,c) < r; }
	bool Wrap(const circle &t)const{ elem d = dist(c,t.c); return d + t.r <= r; }
};

int CircleCross(const circle &c1, const circle &c2, pair<point,point> &p)
{
	elem d = dist( c1.c, c2.c );
	
	if( eqv( c1.c, c2.c ) && eq( c1.r, c2.r ) ){ /* ñÂÌ~ªêv */ return -1; }
	if( eqv( c1.c, c2.c ) ){ /* S¾¯êvµÄ¢é */ return 0; }
	if( d > c1.r + c2.r ){ /* ~ªÝ¢ÉðíçÈ¢ */ return 0; }

	vec ab = c2.c - c1.c;
	elem k = ( sq( c1.r ) - sq( c2.r ) + sq( d ) ) / ( 2 * sq( d ) );
	point t = k * ab + c1.c;
	elem x = sqrt( sq(c1.r) - sq( d * k ) );

	if( eq( x, 0 ) ){ /* ð_ðêÂ¾¯Â */ p.first = t; return 1;
	}else{ /* ð_ðñÂÂ */
		vec abr = unormr( ab ); vec abl = unorml( ab );
		vec vp1 = x * abr; vec vp2 = x * abl;
		p.first = vp1 + t; p.second = vp2 + t;
		return 2;
	}
}

struct point_on_circle{
	point p;
	circle c; // ð_pª®·é~
};

struct circle_info{
	circle c;
	vector< point_on_circle > cross_points;
};

void center_point( const point_on_circle &p1, const point_on_circle &p2, pair<elem,elem> &p_arc, pair<point,point> &p_center )
{
	vec v1(p1.p - p1.c.c);
	vec v2(p2.p - p2.c.c);

	vec c_p = p1.c.r * uvec( v1 + v2 ) + p1.c.c;
	p_center.first = c_p;
	p_arc.first = p1.c.r * rad( v1, v2 );

	vec c_n = p1.c.r * (-uvec( v1 + v2 ) ) + p1.c.c;
	p_center.second = c_n;
	p_arc.second = p1.c.Perimeter() - p_arc.first;

	if( 0 < cross( v1, v2 ) ){
		swap(p_arc.first, p_arc.second);
		swap(p_center.first, p_center.second);
	}
}

bool PointsClkws(const point_on_circle &p1, const point_on_circle &p2)
{
	vec t(0,1);
	vec v1(p1.p-p1.c.c);
	vec v2(p2.p-p2.c.c);
	elem rad1 = rad( v1, t );
	elem rad2 = rad( v2, t );
	if( cross(v1,t) < 0 )
		rad1 = 2 * PI - rad1;
	if( cross(v2,t) < 0 )
		rad2 = 2 * PI - rad2;

	return rad1 < rad2;
}

int main()
{
	while(true){
		int n;
		elem ans = 0;
		vector<circle_info> vc;
		
		scanf("%d", &n);
		if( n == 0 )
			break;
		
		vc.resize(n);
		for(int i = 0; i < n; ++i){
			double x,y,r;
			scanf("%lf%lf%lf", &x, &y, &r);
			vc[i].c.c = complex<elem>(x,y);
			vc[i].c.r = r;
		}

		// ¼Ì~Éàï³êé~ðí
		for(unsigned int i = 0; i < vc.size(); ++i){
			for(unsigned int j = 0; j < vc.size(); ++j){
				if( i != j ){
					if( vc[j].c.Wrap( vc[i].c ) ){
						vc.erase( vc.begin() + i );
						i = -1;
						break;
					}
				}
			}
		}
		
		// ~¯mÌð_ðßé
		for(unsigned int i = 0; i < vc.size(); ++i){
			for(unsigned int j = 0; j < vc.size(); ++j){
				if( i != j ){
					pair<point,point> p;
					int t = CircleCross( vc[i].c, vc[j].c, p );
					point_on_circle p1, p2;
					
					p1.c = vc[i].c;
					p1.p = p.first;
					p2.c = vc[i].c;
					p2.p = p.second;
					
					if( t <= 1 ){
						continue;
					}else{
						vc[i].cross_points.push_back( p1 );
						vc[i].cross_points.push_back( p2 );
					}
				}
			}
		}

		// d¡·é¤L_ðí
		for(unsigned int i = 0; i < vc.size(); ++i){
			for(unsigned int j = 0; j < vc[i].cross_points.size(); ++j){
				for(unsigned int k = j + 1; k < vc[i].cross_points.size(); ++k){
					if( eqv( vc[i].cross_points[j].p, vc[i].cross_points[k].p ) ){
						vc[i].cross_points.erase( vc[i].cross_points.begin() + k );
						--k;
					}
				}
			}
		}
		
		// ¤L_ðvñèÉ®ñ
		for(unsigned int i = 0; i < vc.size(); ++i){
			sort( vc[i].cross_points.begin(), vc[i].cross_points.end(), PointsClkws );
		}

		// solve
		for(unsigned int i = 0; i < vc.size(); ++i){
			ans += vc[i].c.Perimeter();
			if( vc[i].cross_points.size() > 1 ){
				for(unsigned int j = 0; j < vc[i].cross_points.size(); ++j){
					unsigned int mod = vc[i].cross_points.size();
					pair<elem, elem> p_arc;
					pair<point, point> p_center;
					
					center_point( vc[i].cross_points[j % mod], vc[i].cross_points[(j+1) % mod], p_arc, p_center );

					for(unsigned int k = 0; k < vc.size(); ++k){
						if( i != k ){
							if( vc[k].c.Inside( p_center.first ) ){
								ans -= p_arc.first;
								break;
							}
						}
					}
				}
			}
		}

		printf("%.12lf\n", ans);
	}
	return 0;
}