Description

在每台有故障的自动取款机上都贴着一个标签，提示客户去最近的取款机上取款。已知$n$台自动取款机的二维位置列表，为每台自动取款机都找到一个距离最近的自动取款机。

Format

Input

第1行包含测试用例数$T（T≤15）$，每个测试用例都以取款机的数量$n$开始$（2≤n≤10^5）$。接下来的$n$行，每行都包含一台取款机的坐标$x、y（0≤x,y≤10^9）$。在一个测试用例中没有两个点重合。

Output

对每个测试用例，都输出$n$行，第$i$行表示第$i$个取款机与最近取款机的平方距离。

Samples

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

来源

HDU2966