가장 가까운 K개의 행성 쌍

상상으로 만든 우주가 하나 있다. 이 우주는 평면이고, 행성은 평면 위의 점 하나로 나타낸다. 행성마다 사람이 한 명씩 살며, 이들은 대단히 영리하고 죽지 않는다. 행성은 한자리에 붙박여 있어서 서로 만날 방법이 없었는데, 사람들은 자기 행성을 로켓으로 개조해 다른 행성 쪽으로 움직이기 시작했다.

누가 먼저 만나는지 지켜보다가 지루해져서, 모든 행성의 좌표를 컴퓨터에 넣고 가장 가까운 두 행성을 찾아보았다. 이 문제는 너무 흔해서 재미가 없었다. 그래서 문제를 바꾸었다. 서로 다른 두 행성으로 이루어진 쌍을 모두 생각하고, 그중 거리가 짧은 쪽부터 $K$개의 거리를 구한다.

행성의 좌표가 주어질 때 이 $K$개의 거리를 거리의 제곱으로 출력하는 프로그램을 작성하시오. 서로 다른 두 쌍의 거리가 같으면 각각을 따로 세어 쌍의 개수만큼 출력한다.

첫째 줄에 질의의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 질의의 첫째 줄에는 행성의 개수 $N$과 구해야 할 쌍의 개수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 5 \times 10^4$, $1 \le K \le 4$)

이어지는 $N$개의 줄에는 $i$번째 행성의 좌표 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. ($1 \le X_i, Y_i \le 10^6$)

모든 좌표는 정수이다. 좌표가 같은 행성은 없고, 서로 다른 두 행성으로 이루어진 쌍의 개수는 항상 $K$ 이상이다.

각 질의마다 한 줄씩 출력한다. $i$번째 질의의 줄은 case i: 로 시작하고, 그 뒤에 거리가 짧은 쪽부터 $K$개의 거리의 제곱을 공백 하나로 구분해 차례로 출력한다. 질의 번호 $i$는 1부터 센다.