Minimum Triangle Perimeter

You are given a set of points whose coordinates are all integers. Pick three distinct points of the set to form a triangle, and find the smallest perimeter such a triangle can have.

A triangle whose three points lie on one line and whose area is zero still counts. The perimeter is the sum of the three pairwise Euclidean distances.

The first line holds the number of test cases, $T$. $T$ test cases follow.

The first line of each test case holds $n$, the number of points in the set. Each of the next $n$ lines holds two integers $x_i$ and $y_i$, the coordinates of the $i$-th point. No two points share the same coordinates.

Limits

• $1 \le T \le 15$
• $0 \le x_i, y_i \le 10^9$
• $3 \le n \le 10^6$

For each test case, print one line in this format.

Case #X: Y

$X$ is the test case number starting at 1 and $Y$ is the minimum perimeter. Print $Y$ with exactly six digits after the decimal point, rounding the seventh digit half up.