Closest Point

You are given $N$ points on a 2D plane. Let the coordinates of point $i$ be $(x_i, y_i)$.

For two points $i$ and $j$, define the distance as

$\operatorname{dist}(i, j) = (x_j - x_i)^2 + (y_j - y_i)^2$

that is, the squared Euclidean distance between the two points.

For each point $i$, find and print the minimum distance to any other point:

$\min_{1 \le j \le N,\ j \ne i} \operatorname{dist}(i, j)$

The input consists of several test cases.

The first line contains the number of test cases $T$ ($1 \le T \le 15$).

For each test case, the first line contains the number of points $N$ ($2 \le N \le 10^5$). Each of the following $N$ lines contains the coordinates $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$) of a point, separated by a space.

For each test case, print $N$ lines.

The $i$-th line must contain the value of $\min_{1 \le j \le N,\ j \ne i} \operatorname{dist}(i, j)$ for point $i$.

Two distinct points may share the same location; in that case the value is $0$.