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

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

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

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

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

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

Выведите в i-ой строке общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.

Пример

После того, как добавлены первые 4 коровы, корове в ячейке (1, 1) стало комфортабельно.

После того, как добавлены первые 7 коров, корове в ячейке (2, 1) стало комфортабельно.

После того, как добавлены первые 8 коров, корове в ячейках (2, 1) и (2, 2) стало комфортабельно.