Chess Association has decided to equip all of its employees such telephone numbers that are typed on the button to move the phone a knight. For example, the progress of the knight is dialed telephone 340-4927. At the same phone number can not begin with any digit 0 or the digit 8.
The keypad looks like this:
Write a program that determines the number of phone numbers of length N, recruited the course of a knight.
The input file contains an integer n (1 ≤ n ≤ 100).
Derive the output file the required number of telephone numbers.