X Marks the Spot

King Tyrone conquered the nation of Carrania, and his four sons immediately started to argue about how to split the land. The argument is about the gold mines. There are $4N$ of them, and each son must end up with exactly $N$.

The king draws an X on the map. The X is a pair of perpendicular straight lines that cuts the nation into four parts, one part per son. No gold mine may lie on a border, and each of the four parts must contain exactly $N$ gold mines.

The direction of the X is written as an integer vector $(d_x, d_y)$. One border is a line with direction vector $(d_x, d_y)$, and the other border is a line with direction vector $(-d_y, d_x)$. The minister may put the intersection point of the two borders anywhere.

A vector $(d_x, d_y)$ is good if the two perpendicular lines with these directions can be placed so that no gold mine lies on a border and each of the four parts holds exactly $N$ gold mines.

Turning a direction vector by $90$ degrees or flipping its sign gives the same X, so only vectors with $d_x \ge 1$, $-d_x < d_y \le d_x$ and $\gcd(d_x, |d_y|) = 1$ are considered. Every X that has an integer direction vector has exactly one representative in this range.

Find the good vector with the smallest $d_x^2 + d_y^2$. If several good vectors share that value, take the one with the smallest $d_y$.

The first line contains the number of test cases $T$. Each test case starts with a line containing $N$, the number of gold mines each son must get. The next $4N$ lines each contain two integers $x_i$ and $y_i$, the coordinates of one gold mine.

Limits

• $1 \le T \le 20$
• $1 \le N \le 250$
• $-10^6 \le x_i, y_i \le 10^6$
• No three gold mines are collinear.
• A good vector with $d_x^2 + d_y^2 \le 200$ always exists.

For each test case, print one line in the form Case #x: dx dy. Here $x$ is the test case number starting from $1$, and $d_x$ and $d_y$ are the good vector with the smallest $d_x^2 + d_y^2$, with ties broken by the smallest $d_y$.