题目描述

小 Z 的学校举办运动会啦，现在小 Z 的班级准备一个方阵阵型（可以想象成一个无限大的棋盘）来参加检阅，他们都穿着白色衣服。

小 Z 的班主任觉得如果所有同学都穿着同样颜色衣服的话，会显得十分单调。现在班主任决定依次指派 $N$ 名同学的衣服换为红色，每名同学的位置以 $(x_i, y_i)$ 给出。如果某个穿红衣服同学的水平或竖直方向上恰好与其他三个穿红色衣服的同学相邻，则这名同学正处于"完美"状态。

现在小 Z 想计算，在班主任每指派一名同学将衣服换为红色后，处于“完美”状态同学的数量。

输入格式

输入的第一行包含一个整数 $N$ ，表示将要更换多少名同学的衣服。

以下 $N$ 行每行包含两个空格分隔的整数，表示将要更换坐标 $(x,y)$ 的同学的衣服。

输出格式

输出的第 $i$ 行包含前 $i$ 名同学改变为红色衣服之后，处于“完美”状态的同学的数量。

输入输出样例

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

0
0
0
1
0
0
1
2

提示

【样例解释】

在前 $4$ 名同学改变为红色衣服之后，位于 $(1,1)$ 的同学是完美的。

在前 $7$ 名同学改变为红色衣服之后，位于 $(2,1)$ 的同学是完美的。

在前 $8$ 名同学改变为红色衣服之后，位于 $(2,1)$ 和 $(2,2)$ 的同学是完美的。

【数据范围】

对于所有数据点，满足$1≤N≤10^5,0≤x,y≤1000$，并且，输入保证所有方格的坐标是不同的。

具体数据分布如下：

• 测试点 1-4 满足 $N≤400$。
• 测试点 5-12 没有额外限制。