금광을 나누는 X

타이론 왕은 카라니아를 정복했고, 네 아들은 곧바로 땅을 어떻게 나눌지 다투기 시작했다. 다툼의 초점은 금광이다. 금광은 모두 $4N$개이고, 네 아들이 각각 정확히 $N$개씩 받아야 한다.

왕은 지도 위에 X를 긋는다. X는 서로 수직인 두 직선이며, 나라를 네 구역으로 나눈다. 아들 한 명이 한 구역을 받는다. 어떤 금광도 경계선 위에 있으면 안 되고, 네 구역에는 각각 금광이 정확히 $N$개 들어가야 한다.

X의 방향은 정수 벡터 $(d_x, d_y)$로 나타낸다. 한 경계선은 방향 벡터가 $(d_x, d_y)$인 직선이고, 다른 경계선은 방향 벡터가 $(-d_y, d_x)$인 직선이다. 두 경계선이 만나는 점은 어디에 두어도 된다.

벡터 $(d_x, d_y)$가 조건을 만족한다는 것은, 이 두 방향을 가지는 수직인 두 직선을 적당한 위치에 놓아서 어떤 금광도 경계선 위에 오지 않고 네 구역이 각각 금광을 정확히 $N$개 담도록 만들 수 있다는 뜻이다.

방향 벡터를 $90$도 돌리거나 부호를 뒤집어도 같은 X가 되므로, $d_x \ge 1$, $-d_x < d_y \le d_x$, $\gcd(d_x, |d_y|) = 1$인 벡터만 생각한다. 정수 방향 벡터로 나타낼 수 있는 X는 이 범위에 표현이 정확히 하나 있다.

조건을 만족하는 벡터 중에서 $d_x^2 + d_y^2$이 가장 작은 것을 구하라. 그런 벡터가 여럿이면 $d_y$가 가장 작은 것을 고른다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 아들 한 명이 받아야 할 금광의 수 $N$이 주어진다. 이어지는 $4N$개의 줄에는 금광 하나의 좌표 $x_i$와 $y_i$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 20$
• $1 \le N \le 250$
• $-10^6 \le x_i, y_i \le 10^6$
• 한 직선 위에 놓인 금광이 세 개 이상 있는 경우는 없다.
• $d_x^2 + d_y^2 \le 200$이면서 조건을 만족하는 벡터가 항상 존재한다.

각 테스트 케이스마다 Case #x: dx dy 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이다. $d_x$와 $d_y$는 조건을 만족하는 벡터 중 $d_x^2 + d_y^2$이 최소인 것이고, 최소인 벡터가 여럿이면 $d_y$가 가장 작은 것이다.