Пастбище Фермера Нхой может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

ФН добавит n коров на пастбище одну за другой. i-ая корова займёт ячейку (xi, yi), которая отличаетсяот ячеек, занятых всеми другими коровами.

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому ФН хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале 0..1000.

Для каждого i в интервале 1..n, выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы 1..i.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 105). Каждая из следующих n строк содержит по 2 целых числа, указывающих (x, y) (0 ≤ x, y ≤ 1000) координаты ячейки с коровой.

Выходные данные

Выведите минимальное количество коров, которое ФН должен добавить, для каждого i в интервале 1..n, на отдельной строке.

Пример

Для i = 4, ФН должен добавить корову в позицию (2, 1), чтобы сделать корову в позиции (1, 1) некомфортабельной.

Для i = 9, лучшее что ФН может сделать - добавить коров в позиции (2, 0), (3, 0), (2, −1), (2, 3).