그 시절 학창 시절

이것은 격자판 위에서 하는 게임이다. 두 플레이어는 먼저 격자점 몇 개를 표시한 뒤, 동전을 던져 누가 먼저 할지 정한다. 각 차례에 플레이어는 네 점 $A$, $B$, $C$, $D$를 표시하고, $(A, B)$, $(B, C)$, $(C, D)$, $(D, A)$를 이어 사각형을 그린다. 그 사각형 넓이의 두 배가 그 플레이어의 점수에 더해지고, 차례가 상대에게 넘어간다. (넓이의 두 배를 쓰는 것은 점수를 항상 정수로 만들기 위함이다.)

이미 그려진 것과 같은 사각형은 다시 그릴 수 없다. 다만 이전에 사용한 점은 다시 사용할 수 있다. 예를 들어 다섯 점 $P, Q, R, S, T$가 있을 때, 첫 번째 플레이어가 $(A, B, C, D) = (P, Q, R, S)$를 그렸다면, 두 번째 플레이어는 $(A, B, C, D) = (R, S, P, Q)$를 그릴 수 없다. 두 표기가 같은 사각형을 나타내기 때문이다.

같은 네 점으로 만든 두 사각형은 서로 같은 사각형으로 본다. 따라서 네 점으로 이루어진 한 집합은 최대 한 번만 그릴 수 있고, 그 집합을 선택한 플레이어는 넓이가 최대가 되도록 점들을 잇는다. 결국 각 네 점 집합은 자신의 가장 큰 사각형만을 합계에 기여한다.

두 플레이어 모두 자신의 점수를 최대로 하도록 최적으로 플레이한다. 서로 다른 $N$개의 점의 좌표가 주어질 때, 두 플레이어 점수의 합을 구하여라.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다 ($T \le 50$).

각 테스트 케이스의 첫째 줄에는 양의 정수 $N$이 주어진다 ($N \le 700$). 이어서 $N$개의 점의 좌표가 각각 $x\ y$ 쌍으로 주어진다. 각 좌표의 절댓값은 최대 $10^6$까지 될 수 있다. 퇴화된 사각형을 만들 수 없도록, 어떤 세 점도 한 직선 위에 있지 않다.

각 테스트 케이스마다 Case x: s를 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, s는 점수의 합을 $1000003$으로 나눈 나머지이다. 합이 매우 클 수 있으므로 반드시 나머지를 출력한다.