题目描述

你参加一场定向越野比赛。比赛要求从二维平面原点出发，按顺序经过 $N$ 个检查点，最后返回原点，目标是最小化总移动距离。

每个检查点都是一个边与坐标轴平行的矩形。第 $i$ 个检查点是以如下四点为顶点的矩形内部及边界：

[ (L_i,B_i),(R_i,B_i),(R_i,T_i),(L_i,T_i) ]

形式化地，当且仅当同时满足以下两个条件时，认为你通过了第 $i$ 个检查点：

1. 若 $i\ge 2$，则第 $i-1$ 个检查点已经通过；
2. 当前坐标 $(x,y)$ 满足 $L_i\le x\le R_i$ 且 $B_i\le y\le T_i$。

如果在未满足条件 1 的情况下进入某个检查点，或再次进入已通过的检查点，都不会发生任何事情。

你可以在平面上自由移动。请求出从原点出发，按顺序通过所有检查点并返回原点的最短距离。

保证：

• 任意两个检查点没有公共点；
• 任意检查点都不包含原点。

输入格式

输入包含不超过 50 个数据集。

每个数据集格式如下：

N
L_1 R_1 B_1 T_1
L_2 R_2 B_2 T_2
...
L_N R_N B_N T_N

输入以一行 0 结束。

输出格式

对于每个数据集，输出一行，表示完成比赛所需的最短距离。

答案允许绝对误差或相对误差不超过 $10^{-6}$。

数据范围

• $1 \le N \le 9$；
• $-10000 \le L_i < R_i \le 10000$；
• $-10000 \le B_i < T_i \le 10000$；
• 任意两个检查点没有公共点；
• 任意检查点都不包含原点；
• 数据集数量不超过 $50$。

样例输入

2
1 2 -1 2
-2 -1 -2 2
2
1 2 1 2
-2 -1 -2 2
2
3 4 -2 2
1 2 -1 2
3
15 20 0 14
-5 15 15 20
-15 -5 0 14
0

样例输出

4
4.576491223
6
50