在一个无限的二维平面上，存在一个不透明的障碍物和一个单面镜。障碍物可以表示为一个三角形，镜子可以表示为一个从 $(x_{m,1}, y_{m,1})$ 指向 $(x_{m,2}, y_{m,2})$ 的有向线段，其右侧具有反射性。

有 $m$ 块石头位于点 $(x_1, y_1)$，DreamGrid 想要将所有石头移动到点 $(x_2, y_2)$。必须满足以下约束：

• DreamGrid 每次只能携带一块石头。
• 一旦 DreamGrid 捡起一块石头，他只能将其放下在点 $(x_2, y_2)$。
• 设 $L$ 为 DreamGrid 行走的路径，则对于 $L$ 上的每一点 $p$，DreamGrid 都应该能直接或通过镜子看到所有的石头。

注意：

• 如果视线的一部分在障碍物内部（视线穿过障碍物的点或边是可以的），则认为 DreamGrid 无法通过该视线看到石头。
• 如果镜子的两个端点之一在视线上，则认为 DreamGrid 既可以通过镜子看到石头，也可以透过镜子看到石头。
• 反射过程遵循物理定律——入射角等于反射角。入射光线与反射光线相对于镜子位于同一半平面。
• 如果视线与镜子平行，则不会发生反射，且镜子不被视为障碍物。
• DreamGrid 不能进入障碍物内部，但可以在障碍物的边或顶点上移动。
• DreamGrid 不能穿过镜子，但可以在镜子上移动。注意，如果 DreamGrid 在镜子的线段上（非两个端点），他只能看到他来时的那一侧，而不能透过镜子看到另一侧。

DreamGrid 想要知道将所有石头从 $(x_1, y_1)$ 移动到 $(x_2, y_2)$ 的最短距离。

输入格式

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

第一行包含一个整数 $m$ ($1 \le m \le 10^6$)，表示石头的数量。 第二行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$，表示起点和目标点。 第三行包含四个整数 $x_{m,1}, y_{m,1}, x_{m,2}$ 和 $y_{m,2}$，表示镜子的坐标。 接下来的 3 行，每行包含两个整数 $x_i$ 和 $y_i$，表示障碍物的顶点坐标。

所有坐标的绝对值均不超过 100。起点和目标点均在障碍物和镜子之外。镜子和障碍物没有公共点。 保证任意三点不共线。

输出格式

对于每组测试数据，输出一个实数表示最短距离，如果 DreamGrid 无法在满足约束的情况下移动所有石头，则输出 $-1$。

如果你的答案的绝对误差或相对误差小于 $10^{-6}$，则视为正确。

样例

输入 1

2
2
-2 0 2 0
-3 3 3 3
0 1
-3 -2
3 -2
2
-2 0 2 0
-3 3 -1 3
0 1
-3 -2
3 -2

输出 1

13.416407864999
-1

说明

我们欢迎特邀嘉宾 Mashiro，她慷慨地将此题捐赠给我们的题库，并使用她的速写本为我们解释样例测试用例。

在上图中，我们将起点标为点 $A$，目标点标为点 $B$。镜子由从 $M1$ 指向 $M2$ 的线段表示，右侧具有反射性。

对于第一个样例测试用例，最优路径为 $A \to C \to B \to C \to A \to C \to B$。

对于第二个样例测试用例，由于 DreamGrid 无法从 $B$ 看到 $A$，因此在遵循题目描述中约束的前提下，不可能将两块石头从 $A$ 移动到 $B$。