Minimum Triangle Perimeter

You are given a set of points with integer coordinates. Choose three distinct points from the set and report the smallest perimeter their triangle can have.

The perimeter of a triangle is the sum of the three distances between the chosen points. A degenerate triangle, one whose three points lie on a single line and whose area is 0, counts as a triangle.

The first line contains the number of test cases $T$. Then $T$ test cases follow.

The first line of each test case contains the number of points $n$. Each of the next $n$ lines contains two integers $x_i$, $y_i$ separated by a space, 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 10000$

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

Case #X: Y

$X$ is the test case number, counted from 1. $Y$ is the minimum perimeter rounded to six digits after the decimal point. Print all six digits even when they are zeros.