2차원 평면 상에 N개의 점이 주어진다. 

1 ≤ i, j ≤ N에 대해서 dist(i, j) = (x_j - x_i)² + (y_j - y_i)² 라 정의할 때, 각각의 점 i에 대해서, Min(dist(i, j)) (1 ≤ j ≤ N, j ≠ i) 를 출력하라.

입력 형식

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

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

이후 각각의 테스트 케이스마다, 첫 번째 줄에 N (2 ≤ N ≤ 10⁵) 이 주어진다. 이후 N개의 줄에 x, y가 주어진다 (0 ≤ x, y ≤ 10⁹)

출력 형식

각각의 테스트 케이스마다 N줄을 출력하라.

i번째 줄은 Min(dist(i, j)) (1 ≤ j ≤ N, j ≠ i)의 값이어야 한다.

예제 입력

2
10
17 41
0 34
24 19
8 28
14 12
45 5
27 31
41 11
42 45
36 27
15
0 0
1 2
2 3
3 2
4 0
8 4
7 4
6 3
6 1
8 0
11 0
12 2
13 1
14 2
15 0

예제 출력

200
100
149
100
149
52
97
52
360
97
5
2
2
2
5
1
1
2
4
5
5
2
2
2
5