For a region $S$ in a two-dimensional plane, the convex hull is defined as:

$$C(S) = \{p | \exists \alpha \in [0,1], \exists p_1, p_2 \in S, p = \alpha p_1 + (1-\alpha) p_2\}$$

Given $n$ circles $C_1, \ldots, C_n$, let $S = \bigcup_{i=1}^n C_i$, which is the union of all circles. Your task is to find the perimeter of the convex hull $C(C(S))$.

Input Format

• The first line contains an integer $T (1 \leq T \leq 60)$, representing the number of test cases.
• For each test case:
  • The first line contains a positive integer $n$ indicating the number of circles.
  • The following $n$ lines contain three integers $x_i, y_i, r_i(1 \leq r_i \leq 1000, |x_i|, |y_i| \leq 10^3)$, describing a circle.

Output Format

• For each test case, output a single line with a floating-point number representing the perimeter of the convex hull. Your answer will be considered correct if the absolute or relative error does not exceed $10^{-6}$.

Sample

Sample Input

3
2
0 0 1
1 0 1
4
0 0 1
0 1 1
1 0 1
1 1 1
5
0 0 1
2 2 1
0 2 1
2 0 1
1 1 2

Sample Output

8.28318530718
10.28318530718
14.28318530718

Constraints

• For $20\%$ of the data, $n \leq 2$.
• For $50\%$ of the data, $n \leq 3$.
• For $70\%$ of the data, $n \leq 5$.
• For $100\%$ of the data, $n \leq 100$.