K closest planet pairs

You made up a universe. It is flat, and every planet in it is one point on the plane. One person lives on each planet, and those people are extremely clever and never die. The planets sit still, so nobody could visit anyone else, until the people rebuilt their own planets into rockets and started moving toward each other.

Watching to see who meets first got boring, so you loaded every planet's coordinates into your computer and looked for the two closest planets. That question is far too common. So you changed it. Take every pair of two different planets and find the $K$ shortest distances among those pairs.

Given the coordinates of the planets, write a program that prints those $K$ distances as squared distances. If two different pairs have the same distance, count each pair separately and print the value once per pair.

The first line contains the number of queries $T$. ($1 \le T \le 10$)

The first line of each query contains the number of planets $N$ and the number of pairs to find $K$, separated by a space. ($1 \le N \le 5 \times 10^4$, $1 \le K \le 4$)

Each of the next $N$ lines contains the coordinates $X_i$ and $Y_i$ of planet $i$, separated by a space. ($1 \le X_i, Y_i \le 10^6$)

All coordinates are integers. No two planets share the same coordinates, and the number of pairs of two different planets is always at least $K$.

Print one line per query. The line for query $i$ starts with case i: , followed by the $K$ smallest squared distances in non-decreasing order, separated by single spaces. Query numbers start at 1.