Пасовище Фермера Нхой може розглядатися як величезна 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\).

Для кожного \(i\) в інтервалі \(1 \ldots N\), виведіть мінімальну кількість корів, які він повинен додати, щоб не було комфортних корів, якщо вважати, що на пасовищі знаходяться лише корови \(1\ldots i\).

Формат вхідних даних

Перший рядок містить ціле число \(N\). Кожен з наступних \(N\) рядків містить по 2 розділених пробілом цілих числа, що вказують \((x,y)\) координати комірки з коровою.

Формат вихідних даних

Мінімальна кількість корів, яку ФН має додати, для кожного \(i\) в інтервалі \(1 \ldots N\), на окремому рядку.

Приклад вхідних даних

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)\).