Ход конём

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.

Input

The input file contains an integer n (1 ≤ n ≤ 100).

Output

Derive the output file the required number of telephone numbers.

Examples