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<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }

  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }

};

struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator < (const Segment& s) const { return !( p1 == s.p1 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ); }
};

typedef Point Vector;
typedef Segment Line;

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
double norm(Point a){ return a.x*a.x+a.y*a.y; }
double abs(Point a){ return sqrt(norm(a)); }

double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

pair<Point, Point> crosspointCC( Point C1, double r1, Point C2, double r2) {
  complex<double> c1(C1.x,C1.y);
  complex<double> c2(C2.x,C2.y);
  complex<double> A = conj(c2-c1), B = (r2*r2-r1*r1-(c2-c1)*conj(c2-c1)), C = r1*r1*(c2-c1);
  complex<double> D = B*B-4.0*A*C;
  complex<double> z1 = (-B+sqrt(D))/(2.0*A)+c1, z2 = (-B-sqrt(D))/(2.0*A)+c1;
  return pair<Point, Point>(Point(z1.real(),z1.imag()),Point(z2.real(),z2.imag()));
}

bool intersectCC(Point a,double ra,Point b,double rb){
  double d = abs(a-b);
  double r1 = max(ra,rb);
  double r2 = min(ra,rb);

  if( equals(d,r1+r2) ) return false; // 1tenn

  if(!equals(d,r1+r2) && d > r1+r2)return false;
  if(!equals(d,r1-r2) && d < r1-r2)return false;  // verify
  return true;
}

const int MAX_N = 200;
Point cp[MAX_N];
double r[MAX_N];
int n;

Point vir;
bool comp_angle(Point a,Point b) {
  Vector va = a - vir;  
  Vector vb = b - vir;
  return atan2(va.y,va.x) < atan2(vb.y,vb.x);
}

double cw_angle(Point p0,Point p1,Point p2){
  double ret = M_PI - getArg(p0,p1,p2);
  if( ccw(p1,p0,p2) == COUNTER_CLOCKWISE ) ret = 2*M_PI - ret;
  return ret;
}

bool  LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return  equals(a,b) || a < b; }

struct Data {
  Segment seg;
  Point c;
  int index;
  bool operator < ( const Data &data ) const {
    if( seg == data.seg ) return seg < data.seg;
    if( index != data.index ) return c < data.c;
    return index < data.index;
  }
  bool operator == ( const Data &data ) const { return seg == data.seg && c == data.c; }
};

bool check(Data data){
  double arg = cw_angle(data.seg.p2,data.c,data.seg.p1);
  double left_angle = atan2(data.seg.p1.y-cp[data.index].y,data.seg.p1.x-cp[data.index].x);
  if( LT(left_angle,0.0) ) left_angle += 2*M_PI;
  double middle_angle = left_angle + arg / 2.0;
  Point mp = Point(cp[data.index].x+cos(middle_angle)*r[data.index],cp[data.index].y+sin(middle_angle)*r[data.index]);
  assert( equals(abs(cp[data.index]-mp),r[data.index]) );
  rep(i,n) if( i != data.index ) {
    double dist = abs(mp-cp[i]);
    if( LT(dist,r[i]) ) return false;
  }
  return true;
}

bool insideCC(Point a,double ra,Point b,double rb){
  double d = sqrt(norm(a-b));
  double r1 = max(ra,rb);
  double r2 = min(ra,rb);
  if(!equals(d,r1-r2) && d < r1-r2) return ra < rb; 
  return false;
}

double compute(){

  double ret = 0;  
  vector<Data> buf;
  rep(i,n) {
    vector<Point> vp;
    rep(j,n) if( i != j && intersectCC(cp[i],r[i],cp[j],r[j]) ) {
      pair<Point,Point> tmp = crosspointCC(cp[i],r[i],cp[j],r[j]);
      vp.push_back(tmp.first), vp.push_back(tmp.second);
    }
    if( vp.empty() ) { 
      bool failed = false;
      rep(j,n) if( i != j ) if( insideCC(cp[i],r[i],cp[j],r[j]) ) { failed = true; break; }
      if( !failed ) ret += M_PI * r[i] * 2;
      continue; 
    }
    sort(vp.begin(),vp.end());
    vp.erase(unique(vp.begin(),vp.end()),vp.end());
    vir = cp[i];
    sort(vp.begin(),vp.end(),comp_angle);
    rep(j,vp.size()) buf.push_back((Data){Segment(vp[j],vp[(j+1)%(int)vp.size()]),cp[i],i});
  }

  sort(buf.begin(),buf.end());
  buf.erase(unique(buf.begin(),buf.end()),buf.end());

  rep(i,buf.size()) if( check(buf[i]) ) ret += r[buf[i].index] * cw_angle(buf[i].seg.p2,buf[i].c,buf[i].seg.p1);

  
  return ret;
  
}

int main(){
  while( cin >> n, n ){
    rep(i,n) cin >> cp[i].x >> cp[i].y >> r[i];
    printf("%.10lf\n",compute());
  }
  return 0;
}