효율적인 기계

과학자 현우의 실험실은 2D 격자 모양의 "셀"로 구성되어 있습니다. (거대한 체스판을 상상해 보세요). 초기에는 실험실이 비어져 있습니다.

현우는 $N$ ($1 \le N \le 10^5$)개의 기계를 실험실에 하나씩 추가할 계획입니다. $i$번째 기계는 $(x_i,y_i)$ 영역에 위치하며, 이 영역은 다른 모든 기기가 위치한 영역과 다릅니다. ($0 \le x_i,y_i \le 1000$).

'비효율적인' 기계는 기계가 수평이나 수직으로 정확히 세 개의 다른 기계와 인접해 있을 때를 말합니다.  비효율적인 기계들은 전력 소모가 증가합니다. 현우는 비효율적인 기계가 없을 때까지 기계를 계속 추가하려 합니다. 이 때 추가된 기기의 $x$와 $y$ 좌표가 반드시 $0 \ldots 1000$ 범위 내에 위치할 필요는 없습니다.

$1 \ldots N$ 범위 내의 각 $i$에 대해, 초기 실험실에 $1 \ldots i$번째 기계만 있다면 비효율적인 기계가 없을 때까지 현우가 추가로 설치해야 하는 최소한의 기계 수를 출력하세요.

첫 번째 줄에는 단일 정수 $N$이 주어집니다. 다음 $N$개의 줄 각각에는 두 개의 공백으로 구분된 정수가 적혀있고, 이는 기계가 위치한 셀의 $(x,y)$ 좌표를 나타냅니다.

$1 \ldots N$ 범위 내의 각 $i$에 대해, 과학자 현우가 비효율적인 기계가 없을 때까지 추가해야 하는 기계의 최소 수를 $N$개의 별도의 줄에 출력해야합니다.