Задача Ход конем

Описание

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Клавиатура телефона выглядит так:
789
456
123
0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

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

Во входном файле записано целое число N (1≤N≤100).

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

Выведите в выходной файл искомое количество телефонных номеров.