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

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

7 8 9
4 5 6
1 2 3
  0

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

Формат вхідних даних

У стандартному потоці міститься ціле число ~N~ ~(1 ≤ N ≤ 100)~.

Формат вихідних даних

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

Приклад вхідних даних

2

Приклад вихідних даних

16