최소 둘레 삼각형

정수 좌표를 가진 점 집합이 주어진다. 이 집합에서 서로 다른 세 점을 골라 만드는 삼각형의 둘레 중 가장 작은 값을 구하라.

삼각형의 둘레는 고른 세 점 사이의 거리 세 개를 모두 더한 값이다. 세 점이 한 직선 위에 놓여 면적이 0이 되는 경우도 삼각형으로 센다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 점의 개수 $n$이 주어진다. 다음 $n$개의 줄에는 $i$번째 점의 좌표를 나타내는 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다. 같은 좌표에 점이 두 개 이상 있는 경우는 없다.

제한

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

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 테스트 케이스 번호이고 1부터 센다. $Y$는 최소 둘레를 소수점 아래 여섯째 자리까지 반올림한 값이다. 소수점 아래 여섯 자리는 값이 0이어도 모두 적는다.