즉석 야외 갤러리

화가 코디자말은 힙스터 친구들보다 한발 앞서 나가려고 최근 작품을 즉석 야외 갤러리에서 선보이기로 했다. 들판에 나타나 그림 몇 점을 세워 두고 전시할 생각이다.

들판에는 기둥이 $N$개 서 있고, 어떤 세 기둥도 한 직선 위에 있지 않다. 따라서 같은 위치에 있는 두 기둥도 없다. 코디자말은 이 중 네 기둥을 골라 순서대로 $p_1, p_2, p_3, p_4$라 하고, $p_1$과 $p_2$, $p_2$와 $p_3$, $p_3$와 $p_4$, 마지막으로 $p_4$와 $p_1$ 사이에 벨벳 로프를 건다. 어떤 두 로프도 서로 교차하지 않도록 네 기둥과 그 순서를 골라야 한다. 즉 $p_1p_2p_3p_4$는 단순 사각형이어야 한다. 사각형은 볼록해도 되고 오목해도 된다. 그림은 로프로 둘러싸인 영역 안에 건다.

그림을 살 만한 부유한 미술 애호가를 끌어들이려고 코디자말은 방문객에게 다과를 나를 직원을 고용한다. 다과 비용은 정해져 있지만 직원 비용은 직원이 걸어 다녀야 하는 넓이에 비례한다. 직원은 제곱미터당 2 아트코인을 받는다. 그래서 코디자말은 사각형 $p_1p_2p_3p_4$의 넓이를 최소로 하여 다과 서비스 비용(아트코인 단위)을 최소로 하려고 한다. 이 최소 비용을 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 들판에 있는 기둥의 수 $N$이 주어진다. 다음 $N$개의 줄에는 각각 두 정수 $X_i$와 $Y_i$가 주어진다. 이는 $i$번째 기둥의 좌표로, 임의의 원점에서 잰 미터 단위 값이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 코디자말이 내야 하는 최소 아트코인 수이다. 다시 말해 y는 입력으로 주어진 점 중 네 개를 꼭짓점으로 하는 단순 사각형 가운데 가장 작은 것의 넓이(제곱미터)의 두 배이다. 이 값은 항상 정수이다.

• $1 \le T \le 100$
• $4 \le N \le 1000$
• 모든 $i$에 대해 $-10^9 \le X_i \le 10^9$
• 모든 $i$에 대해 $-10^9 \le Y_i \le 10^9$
• 입력의 어떤 세 점도 한 직선 위에 있지 않다.

1번 케이스에서는 입력의 점이 4개뿐이고, 단순 사각형을 이루는 순서는 모두 한 변의 길이가 10인 정사각형을 만든다.

2번과 3번 케이스에서는 첫 번째 점을 빼고 나머지 네 점을 입력에 주어진 순서대로 쓰는 것이 최적 중 하나이다.