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 \textbf{340-4927}. At the same phone number can not begin with any digit \textbf{0} or the digit \textbf{8}. The keypad looks like this: Write a program that determines the number of phone numbers of length \textbf{N}, recruited the course of a knight. \InputFile The input file contains an integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}). \OutputFile Derive the output file the required number of telephone numbers.