Задача D. Конь-шпион

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

На обычной шахматной доске 8 × 8 находится один белый конь и несколько черных ферзей. Конь может перемещаться по обычным правилам, но не может занять поле, если на нём находится ферзь или оно находится под боем ферзя. На скольких полях сможет побывать конь?

Формат входных данных

Первая строка входных данных содержит одно натуральное число n — количество фигур на доске. Во второй строке через пробел приведено n двузначных чисел — координаты фигур. Первые n − 1 чисел соответствуют расстановке ферзей, последнее — коня. Первая цифра числа — номер вертикали, вторая — горизонтали шахматного поля. Гарантируется, что координаты всех фигур различны. Гарантируется, что конь в начальном расположении не находится под боем.

Формат выходных данных

Выведите одно натуральное число — количество различных полей шахматного поля, до которых может добраться конь (включая исходное).

Ограничения

2 ≤ n ≤ 10

Пояснение к примеру

Смотри рисунок. Начальное положение фигур слева. Справа красными значками отмечены поля, находящиеся под боем ферзей. Зелеными значками отмечены поля, до которых конь может добраться. Вместе с исходным полем, всего их пять.

Примеры тестов

Стандартный вход Стандартный выход
1
4
15 48 83 71
5

0.087s 0.017s 15