자유를 향한 회전 (라지)

우주선은 2차원 평면의 원점 $(0, 0)$에서 출발한다. 은하에는 별이 $N$개 있고, $i$번째 별의 위치는 $(X_i, Y_i)$이다.

1분마다 다음 두 가지 중 하나를 한다. 별을 하나 골라 그 별을 중심으로 우주선을 시계 방향으로 90도 회전시키거나, 그 자리에 머문다. 같은 별을 다시 고를 수 있다. 점 $(p, q)$를 $(a, b)$를 중심으로 시계 방향으로 90도 회전시키면 $(a + q - b,\ b - p + a)$가 된다.

주어진 시간은 $M$분이고, 원점에서 가장 멀리 떨어진 곳에서 끝내는 것이 목표이다. 회전은 정수 좌표를 정수 좌표로 옮기므로 원점과 최종 위치 사이의 거리의 제곱은 항상 정수이다. 이 정수를 구하라.

그림은 가능한 경로 하나에서 처음 세 번의 회전을 보여 준다. 노란 점은 별이고, 보라색 점은 우주선의 위치이다. 이 경로가 최적해의 일부라는 뜻은 아니다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 $N$이, 둘째 줄에는 $M$이 주어지고, 다음 $N$개의 줄에는 별 하나의 위치 $X_i$와 $Y_i$가 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $-1000 \le X_i \le 1000$
• $-1000 \le Y_i \le 1000$
• $1 \le M \le 10^6$
• 같은 위치에 있는 별은 없다.
• 원점에 별이 있을 수 있다.

각 테스트 케이스마다 Case #x: S 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $S$는 $M$분 안에 우주선이 원점에서 도달할 수 있는 최대 거리의 제곱이다. $S$는 부호 있는 64비트 정수 범위에 들어간다.