Хід конем

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

Клавіатура телефона виглядає так:

Напишіть програму, яка визначає кількість телефонних номерів довжини N, які набираються ходом коня.

Вхідні дані

У вхідному файлі записано ціле число n (1 ≤ n ≤ 100).

Вихідні дані

Виведіть у вихідний файл шукану кількість телефонних номерів.

Приклади