Шахова асоціація вирішила оснастити всіх своїх співробітників такими телефонними номерами, які б набиралися на кнопковому телефоні ходом коня. Наприклад, ходом коня набирається телефон 340-4927. При цьому телефонний номер не може починатися ні з цифри 0, ні з цифри 8.
Клавіатура телефону виглядає так:
7 8 9
4 5 6
1 2 3
0
Напишіть програму, що визначає кількість телефонних номерів довжини N, набираються ходом коня.
Формат вхідних даних
У стандартному потоці міститься ціле число \(N\) \((1 ≤ N ≤ 100)\).
Формат вихідних даних
У стандартний потік вивести шукану кількість телефонних номерів.
Приклад вхідних даних
2
Приклад вихідних даних
16
Коментарі