对于二维平面上的区域 $S$，其凸包定义为：

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

给定 $n$ 个圆 $C_1, \ldots, C_n$，令 $S = \bigcup_{i=1}^n C_i$ 为所有圆的并集。你的任务是求出凸包 $C(S)$ 的周长。

输入格式

• 第一行包含一个整数 $T (1 \leq T \leq 60)$，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行包含一个正整数 $n$，表示圆的数量。
  • 接下来的 $n$ 行每行包含三个整数 $x_i, y_i, r_i (1 \leq r_i \leq 1000, |x_i|, |y_i| \leq 10^3)$，描述一个圆。

输出格式

• 对于每个测试用例，输出一行浮点数，表示凸包的周长。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

样例输入 1

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

样例输出 1

8.28318530718
10.28318530718
14.28318530718

数据范围

• 对于 $20\%$ 的数据，$n \leq 2$。
• 对于 $50\%$ 的数据，$n \leq 3$。
• 对于 $70\%$ 的数据，$n \leq 5$。
• 对于 $100\%$ 的数据，$n \leq 100$。