GCPC11G - Security Zone

The manager of a large security company has to build a new surveillance system for different sites. A site consists of N objects where each object has its own security circle. At the border of the surveillance system a high voltage fence has to be installed. The security zone inside of the fence has to be connected. Furthermore, all objects and their security circles should be inside the security zone. The security circles of different objects will never overlap or touch. Now the manager needs your help. He asks you for the minimal needed fence length.

example image example image

Input

The first line of the input gives the number of test cases C (0 ≤ C ≤ 100). The first line of each such test case holds the integer N: the number of objects in the current site (0 < N ≤ 25). Each of the following N lines holds three integers xi, yi, and ri that describe an object. The coordinates of the i-th object and the radius for the needed security circle for this object. (|xi|,|yi| ≤ 100, 0 < ri ≤ 100) (The center of the security circle around an object is the position of the object itself.)

Output

For each test case print one line containing the minimal fence length for this case. Your output should have an absolute or relative error of at most 10-7.

Example

Input:
3
3
2 2 1
8 2 1
5 6 1
2
6 4 2
2 4 1
4
2 2 2
6 1 1
5 5 2
1 6 1

Output:
22.2831853072
17.6761051635
25.4247779608

Added by:Adrian Kuegel
Date:2011-07-05
Time limit:1.802s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Alexander Rass)

hide comments
2013-11-01 01:56:44 Jacob Plachta
What data was used here? I tried all of the official data locally, and my solution ran correctly - however, my main loop appears to run forever here.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.