Farmer John의 목초지는 정사각형 칸으로 이루어진 커다란 이차원 격자로 생각할 수 있다. 거대한 체스판을 떠올리면 된다. 처음에 목초지는 비어 있다.

Farmer John은 목초지에 \(N\)마리의 소를 한 마리씩 추가한다. \((1 \le N \le 100,000)\) \(i\)번째 소는 다른 모든 소가 차지한 칸과 서로 다른 \((x_i,y_i)\) 칸을 차지한다. 각 좌표는 \(0 \le x_i,y_i \le 1,000\)을 만족한다.

어떤 소와 가로 또는 세로로 인접한 다른 소가 정확히 세 마리이면, 그 소를 편안한 소라고 한다. Farmer John은 농장에 있는 편안한 소의 수에 관심이 있다.

각 \(1 \le i \le N\)에 대하여, \(i\)번째 소를 목초지에 추가한 직후 편안한 소의 총수를 출력하여라.

입력

첫째 줄에 정수 \(N\)이 주어진다.

다음 \(N\)개의 줄에는 소가 차지할 칸의 좌표 \((x,y)\)를 나타내는 두 정수가 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 칸은 서로 다르다.

출력

\(i\)번째 줄에 처음 \(i\)마리의 소를 목초지에 추가한 직후 편안한 소의 총수를 출력한다.

예제 입력 1

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

예제 출력 1

0
0
0
1
0
0
1
2

예제 설명 1

처음 네 마리의 소를 추가한 뒤에는 \((1,1)\)에 있는 소가 편안한 소이다.

처음 일곱 마리의 소를 추가한 뒤에는 \((2,1)\)에 있는 소가 편안한 소이다.

처음 여덟 마리의 소를 추가한 뒤에는 \((2,1)\)과 \((2,2)\)에 있는 소가 편안한 소이다.

출처

USACO 2021 February Contest, Bronze, Problem 2. Comfortable Cows