BaoBao 在一个无限的二维平面上迷路了！BaoBao 需要从起点 $(a_x, a_y)$ 出发，找到前往位于 $(b_x, b_y)$ 的家的路径。但这对他来说并非易事，因为平面上散布着 $n$ 个圆形障碍物。第 $i$ 个障碍物的圆心位于 $(x_i, y_i)$，半径为 $r_i$。BaoBao 可以自由地在平面上移动，但他的路线不能与任何障碍物相交（但可以相切）。

我们称 BaoBao 成功到达了他的家，当且仅当 BaoBao 的最终位置与 $(b_x, b_y)$ 之间的距离不超过 $R$，且连接 BaoBao 最终位置与 $(b_x, b_y)$ 的线段不与任何障碍物相交（但可以相切）。

BaoBao 急于回家，所以你的任务是帮助 BaoBao 找到一条从 $(a_x, a_y)$ 出发并成功到达他家的最短路径。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 60），表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($0 \le n \le 2$)，表示平面上的障碍物数量。

第二行包含两个整数 $a_x$ 和 $a_y$ ($-10^4 \le a_x, a_y \le 10^4$)，表示 BaoBao 的起点。

第三行包含三个整数 $b_x, b_y$ ($-10^4 \le b_x, b_y \le 10^4$) 和 $R$ ($0 \le R \le 10^4$)，表示 BaoBao 家的位置以及描述中提到的距离限制。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($-10^4 \le x_i, y_i \le 10^4$) 和 $r_i$ ($0 < r_i \le 10^4$)，表示障碍物的圆心和半径。

保证 $(a_x, a_y)$ 和 $(b_x, b_y)$ 均在障碍物外部或边界上，且障碍物之间互不包含、不相交且不相切。

输出格式

对于每组测试数据，输出一行，表示 BaoBao 到达家所需的最短距离。如果你的答案的绝对误差或相对误差小于 $10^{-6}$，则被视为正确。

样例

输入 1

2
1
10 0
0 0 2
6 0 1
0
0 10
0 0 5

输出 1

8.209191463668802
5.000000000000000

说明

上图展示了第一个样例测试数据，其中 $|AD| = 3.8729833462$ $|\widehat{DE}| = 0.4201283344$ $|EF| = 3.9160797831$ 因此答案为 $|AD| + |\widehat{DE}| + |EF| = 8.2091914637$。