Old School Days

This is a game played on a grid board. Two players first mark some grid points, then toss a coin to decide who plays first. On each turn a player marks four points $A$, $B$, $C$, $D$ and draws the quadrilateral formed by joining $(A, B)$, $(B, C)$, $(C, D)$ and $(D, A)$. Twice the area of that quadrilateral is added to the player's score, and the turn passes to the opponent. (Twice the area is used so that every score is an integer.)

A quadrilateral may not be drawn if the same quadrilateral has already been drawn, although points that were used before may be reused. For example, with five points $P, Q, R, S, T$, if the first player draws $(A, B, C, D) = (P, Q, R, S)$, the second player may not draw $(A, B, C, D) = (R, S, P, Q)$, because both describe the same quadrilateral.

Two quadrilaterals built from the same four points count as the same quadrilateral, so each set of four points can be drawn at most once. A player who chooses a set of four points therefore joins them in the order that yields the largest possible area, and each set of four points contributes only its largest quadrilateral to the total.

Both players play optimally to maximize their own score. Given the coordinates of $N$ distinct points, determine the sum of the two players' scores.

The first line contains a positive integer $T$, the number of test cases ($T \le 50$).

For each test case, the first line contains a positive integer $N$ ($N \le 700$). Then follow the coordinates of the $N$ points, each given as a pair $x\ y$. The absolute value of every coordinate can be as large as $10^6$. To guarantee that no degenerate quadrilateral can be formed, no three points are collinear.

For each test case, print Case x: s, where x is the test-case number (starting from 1) and s is the sum of the scores taken modulo $1000003$. Because the sum can be huge, always print it modulo $1000003$.