El campo de pasteo del Granjeor Juan puede ser considerado como una cuadrícula grande de dos dimensiones con "celdas" cuadradas (piense en un tablero de ajedrez inmenso). Inicialmente el campo está vacío.

El Granjero Yuan añadirá ~N~ vacas al campo una por una. La vaca i-ésima ocupará una celda ~(x_i,y_i)~ que es diferente de las celdas ocupadas por otras vaas.

Se dice que una vaca está "confortable" si es adyacente horizontal o verticalmente a exactamente tres otras vacas. Desafortudamente, las vacas que están muy confortables tienden a disminuir su producción lechera, entonces en la Granjero Yuan quiere añadir vacas adicionales hasta que ninguna vaca (incluyendo la vaca que el añada) está confortable. Note que las vacas añadidas no necesitan tener sus coordenadas ~x~ y ~y~ en el rango ~0...1000~.

Para cada ~i~ en el rango ~1...N~, por favor dé como salida el número mínimo de vacas que el Grajero Yuan necesitaría añadir hasta que ninguna vaca está confortable si inicialmente el campo comienza solamente con las vacas ~1...i~.

Entrada

La primera línea contiene un solo entero ~N~. Cada una de las siguientes ~N~ líneas contiene dos enteros separados por enteros, indicando las coordenadas ~(x,y)~ de la celda de una vaca.

Salida

El número mínimo de vacas que el Granjero Yuan necesita añadir por cada ~i~ en ~1...N~, en ~N~ líneas separadas.

Restricciones

• ~1 \leq N \leq 10^5~
• ~0 \leq x_i,y_i \leq 1000~

Ejemplo de Entrada

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

Ejemplo de Salida

0
0
0
1
0
0
1
2
4

Para ~i=4~, el Granjero Juan debe añadir una vaca adicional en ~(2,1)~ para hacer la vaca ~(1,1)~ no confortable.

Para ~i=9~, lo mejor que el Granjero Yuan puede hacer es poner vacas adicionales en ~(2,0), (3,0), (2,-1)~, y ~(2,3)~.

USACO 2021 February Contest, Silver Problem 1. Comfortable Cows.