Knight's Move on Dial Pad#620
Chess Association decided to assign to all its employees such telephone numbers that can be dialed on a keypad phone by moving as a knight would move on a chessboard. For example, the telephone number 340-4927 can be dialed by the knight's moves. A phone number cannot begin with the digit 0 or the digit 8.
The phone keypad looks as follows:
Write a program that determines the number of phone numbers of length that can be dialed using the knight's move.
The input file contains an integer (1 \le n \le 100).
Output the required number of telephone numbers.
Example 1