The Chess Association decided to equip all its employees with such telephone numbers that would be dialed on a push-button telephone with a knight's move. For example, the knight's move calls 340-4927. At the same time, the phone number cannot begin with either the number 0 or the number 8.
The phone keyboard looks like this:
Write a program to determine the number of telephone numbers of length N dialed by the knight.
Input: Input is an integer N (\(1< =N<=50\)).
Output: output the number of phone numbers you are looking for.
Examples