Bounty Hunter Jeong-eun

Jeong-eun is a bounty hunter chasing a criminal. Jeong-eun flies the ship Galchi II and has to visit all $N$ planets scattered over a two dimensional plane, then return to the starting planet. The starting planet is the one with the smallest $x$ coordinate. Jeong-eun is poor but extravagant and wants to keep enough money for expensive beef, so the total travel distance has to be as small as possible.

Jeong-eun is also chasing the crime syndicate CTP, and restricts the route to avoid being spotted. From the starting planet to the planet with the largest $x$ coordinate, the ship moves only in increasing order of $x$. Coming back from there to the starting planet, it moves only in decreasing order of $x$. The two legs together visit every planet exactly once. The planet with the smallest $x$ coordinate and the planet with the largest $x$ coordinate are the turning points shared by both legs, and every other planet belongs to exactly one leg. When $N = 2$ the route goes from the left planet to the right planet and straight back.

The distance between two planets is the Euclidean distance. Find the shortest total length among the routes that satisfy the rule.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case contains the number of planets $N$ ($2 \le N \le 512$). Each of the next $N$ lines contains the coordinates $x$ and $y$ ($0 \le x, y \le 5000$) of one planet, separated by a space.

All coordinates are integers. Within one test case the $x$ coordinates are distinct, and the planets are given in increasing order of $x$.

For each test case, print the length of the shortest route on its own line.

Round the length at the fourth decimal place and print exactly four digits after the decimal point. Pad with zeros even when the value is an integer, as in 400.0000. The output is compared as an exact string.