为了帮助客户应对出现故障的自动取款机（ATM），Planar 银行的董事会决定在每台 ATM 上贴上一个标签，表达银行对故障的真诚歉意和遗憾。同时，该标签还会温柔地请客户冷静地前往最近的另一台 ATM（希望它能正常工作）。

为此，银行准备了一份包含所有 $n$ 台 ATM 二维坐标的列表。你的任务是为每台 ATM 找到在欧几里得距离下距离它最近的另一台 ATM。

输入格式

输入包含多个测试用例。第一行包含接下来的测试用例数量 $t$ ($t \le 15$)。

每个测试用例以自动取款机的数量 $n$ ($2 \le n \le 10^5$) 开始。

接下来的 $n$ 行中，每行包含一台自动取款机的坐标 $x, y$ ($0 \le x, y \le 10^9$)，由空格隔开。同一个测试用例中不会有两台 ATM 的坐标重合。

输出格式

对于每个测试用例，输出 $n$ 行。其中第 $i$ 行应包含输入的第 $i$ 台 ATM 与其最近邻居之间的距离平方。

样例

输入样例 1

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

输出样例 1

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