최소 둘레

정수 좌표를 갖는 점들의 집합이 주어진다. 이 점들의 집합에서 서로 다른 정점을 갖는 삼각형의 가장 작은 둘레를 계산해야 한다.

제한

메모리 제한: 1 GB.

1 <= T <= 15 0 <= $x_{i}$, $y_{i}$ <= $10^{9}$

작은 데이터 세트

시간 제한: 60초. 3 <= n <= 10000

큰 데이터 세트

시간 제한: 120초. 3 <= n <= 1000000

입력 데이터의 첫 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 집합에 있는 점의 수를 나타내는 정수 n이 주어진다. 이어지는 n개의 줄에는 각각 두 정수 $x_{i}$, $y_{i}$가 주어진다. 이는 i번째 점의 좌표이다. 동일한 좌표에 둘 이상의 점이 있을 수 없다.

각 테스트 케이스마다 다음을 출력한다:

Case #X: Y

여기서 X는 테스트 케이스의 번호이고 Y는 최소 둘레이다. 상대 오차 또는 절대 오차가 최대 10^{-5}인 답은 정답으로 간주한다. 넓이가 영인 삼각형인 퇴화 삼각형도 허용된다.