Twirling Towards Freedom (Large)

Your spaceship starts at the origin $(0, 0)$ of a two-dimensional plane. The galaxy holds $N$ stars, and star $i$ is at $(X_i, Y_i)$.

Each minute you do exactly one of two things: pick a star and rotate the ship 90 degrees clockwise around that star, or stay where you are. You may pick the same star again later. Rotating a point $(p, q)$ by 90 degrees clockwise around $(a, b)$ moves it to $(a + q - b,\ b - p + a)$.

You have $M$ minutes, and you want to finish as far from the origin as possible. A rotation sends integer coordinates to integer coordinates, so the squared distance between the origin and the final position is always an integer. Report that integer.

The picture shows the first three rotations of one possible path. The yellow dots are stars and the purple dots are positions of the ship. This path is not necessarily part of an optimal solution.

The first line has the number of test cases $T$. The test cases follow. The first line of a test case has $N$, the second line has $M$, and each of the next $N$ lines has two integers $X_i$ and $Y_i$, the position of one star.

Limits

• $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$
• No two stars are at the same location.
• A star may be at the origin.

For each test case, print one line in the form Case #x: S, where $x$ is the test case number starting from 1 and $S$ is the square of the largest distance from the origin that the ship can reach within $M$ minutes. $S$ fits in a signed 64-bit integer.