가까운 점 찾기

2차원 평면 위에 $N$개의 점이 주어진다. 점 $i$의 좌표를 $(x_i, y_i)$라고 하자.

두 점 $i$, $j$ 사이의 거리를 다음과 같이 정의한다.

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

즉, 두 점 사이의 유클리드 거리의 제곱이다.

각각의 점 $i$에 대하여, 자기 자신을 제외한 다른 모든 점까지의 거리 중 최솟값

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

을 구하여 출력하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

첫 번째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 15$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 점의 개수 $N$ ($2 \le N \le 10^5$)이 주어진다. 이어지는 $N$개의 줄에는 각 점의 좌표 $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^9$)가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 $N$개의 줄을 출력한다.

$i$번째 줄에는 점 $i$에 대한 $\min_{1 \le j \le N,\ j \ne i} \operatorname{dist}(i, j)$의 값을 출력한다.

서로 다른 두 점이 같은 위치에 있을 수도 있으며, 이 경우 그 값은 $0$이다.