占星家们对他们的黄道十二宫星座预测进行了严谨的科学审视，发现他们的方法在预测未来方面并不比随机猜测更准确。他们没有向内反思，而是将无法预测未来的原因归咎于星星和星座的历史构造。他们正在测试一种构建星座的新方法，这将重塑他们预见未来的能力。

他们需要你的帮助来实现他们的迭代星座创建系统。最初，每颗星星都代表一个独立的星座。在每一步中，你应该通过选择彼此距离最近的两个星座，将它们合并为一个星座。两个星座 $A$ 和 $B$ 之间的距离定义为来自每个星座的星星对的平均欧几里得距离的平方：

$$d(A, B) = \frac{1}{|A||B|} \sum_{a \in A} \sum_{b \in B} ||a - b||^2$$

如果有多个星座对的距离相同，你应该优先合并较旧的星座。在比较可以合并的两对星座时，首先比较星座之间的距离。如果两对星座的距离完全相同，则比较一对中较旧星座的年龄。如果仍然平局，则比较一对中较新星座的年龄。星座的年龄定义为它在最后一次合并时形成的时间，或者对于单星星座，定义为该星星的年龄。输入中的星星按从最老到最年轻的顺序排列。

输入格式

第一行包含星星的数量 $N$。接下来的 $N$ 行包含星星的坐标，每行有两个用空格分隔的整数 $X_i$ 和 $Y_i$。

数据范围

• $2 \le N \le 2000$
• $-1000 \le X_i, Y_i \le 1000$，对于所有 $1 \le i \le N$
• 所有点对 $(X_i, Y_i)$ 都是唯一的，因为物理上不可能有两颗星星位于同一点。

输出格式

在描述的星座创建系统的每一步之后，输出新创建的星座的大小。你应该输出 $N - 1$ 行。

样例

输入 1

3
0 0
-1 0
10 10

输出 1

2
3

输入 2

4
0 0
0 -1
0 1
0 2

输出 2

2
2
4

输入 3

4
0 0
0 1
0 -1
0 2

输出 3

2
3
4