Detour Buster

A parcel-delivery company employs cyclists to deliver packages across a large metropolitan city and pays each cyclist according to the total distance travelled. Every company bicycle carries a GPS unit that records its position once every few seconds. The sequence of recorded positions for one delivery is called a track, and the length of a track -- the sum of the Euclidean distances between consecutive recorded points -- is used to compute the cyclist's pay.

A recent audit revealed that some tracks self-intersect, which means some cyclists made unnecessary detours. Write a program that, given a track, computes the length of the shortest possible route from the first recorded point to the last. The route must lie entirely on the original track and may travel along it in either the same or the opposite direction.

The first line contains an integer $T$, the number of tracks to process.

Each track begins with a line containing a positive integer $N$, the number of recorded points that define the track. Each of the next $N$ lines contains two integers separated by a single space, giving the $x$- and $y$-coordinates (in metres) of a point on the track. The points are listed in the order they were recorded.

Two consecutive points form a segment. Consecutive points are at most 30 metres apart, and each segment intersects at most 20 other segments. All coordinates are integers between -10,000,000 and 10,000,000 inclusive, and $N$ satisfies $1 \le N \le 100000$.

For each track, output on its own line a single integer: the length of the shortest route, in metres, rounded to the nearest integer.

Rounding a positive number $R.xyz$ to the nearest integer:

• if the first decimal digit $x$ is less than 5, the rounded value is $R$;
• otherwise the rounded value is $R+1$.