eolymp
bolt
Try our new interface for solving problems
Problems

Detour Buster

Detour Buster

Time limit 1 second
Memory limit 64 MiB

The Green Parcel Services company employs cyclists to deliver parcels across a large metropolitan city, and employees are paid according to the distances they must travel to deliver parcels. Each company bicycle has been equipped with a global positioning system that records its position once every couple of seconds. The sequence of positions for one delivery is called a track and the length of a track, which is the sum of euclidean distances between consecutive pairs of recorded points, is used to calculate the employee's payment.

A recent audit of the recorded tracks revealed that some tracks self-intersect, which indicates that some employees are making unnecessary detours. Your task is to write a program to process a given track and calculate the length of the shortest possible track from the first to the last point of the original track. The shortest possible track must be part of the original track and may include travelling in the same or opposite direction along the original track.

Input data

Input starts with an integer, on a line by itself, that represents the number of tracks tobe shortened. The description of each track begins with a positive integer N, on a line by itself, representing the number of recorded points that define the track. Each of the following N lines contains two integers, separated by a single space, that define the x and y-coordinates of a point on the track in metres. The points are listed in order of their appearance on the track.

Two successive points, which form a segment, will be no more than thirty metres apart and a segment will not intersect more than twenty other segments. All x- and y-coordinates have values between -10000000 and 10000000, inclusive. N has values between 1 and 100000, inclusive.

Output data

For each input track, the output consists of a single integer, on a line by itself, which is the length of the shortest track in metres. The answer must be rounded to the nearest integer value. Reminder: Rounding a positive number R.xyz to the nearest integer:

  • If the first decimal place (that is x) is less than 5, then the rounded value is R.

  • Otherwise, the rounded value is R+1.

Examples

Input example #1
31
5
0 0
12 0
20 0
10 10
10 -10
6
0 0
15 0
10 -5
4 1
10 1
10 -10
Output example #1
20
17
Source The 2011 South Pacific Programming Contest