该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

王洋教练带领的 LPL 战队终于杀入了英雄联盟 S16 全球总决赛的决赛现场。比赛场馆的选手区可以看作是一个巨大的二维网格，就像一个巨大的棋盘。最初，选手区是空的。

王洋教练会依次安排 N 名（1≤N≤10⁵）队员和工作人员进入选手区就座。第 i 个人会坐在一个与其他所有人都不同的单元格 (xi, yi) 上（0≤xi, yi≤1000）。

一个座位被认为是"过于舒适"的，如果它在水平或垂直方向上恰好与三个其他有人的座位相邻。不幸的是，坐在过于舒适座位上的选手容易放松警惕，影响比赛状态。因此，王洋教练需要安排更多的替补队员和工作人员就座，直到没有任何一个座位（包括后来安排的）是过于舒适的。注意，后来安排的人员的 x 和 y 坐标不一定需要在 0…1000 的范围内。

对于 1…N 中的每个 i，请输出如果最初选手区只有前 i 个人，王洋教练最少需要额外安排多少人就座才能消除所有过于舒适的座位。

输入格式：

第一行包含一个整数 N。接下来的 N 行，每行包含两个空格分隔的整数，表示一个人的座位坐标 (x, y)。

输出格式：

对于 1…N 中的每个 i，在单独的一行上输出王洋教练需要额外安排的最少人数。

样例：

9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1

0
0
0
1
0
0
1
2
4

提示

对于 i=4，王洋教练必须在 (2,1) 位置安排一个额外的人，才能让 (1,1) 位置的座位不再过于舒适。

对于 i=9，王洋教练最好的做法是在 (2,0)、(3,0)、(2,-1) 和 (2,3) 位置安排额外的人员。