eolymp
bolt
Try our new interface for solving problems
Problems

Ход конём

Ход конём

Time limit 1 second
Memory limit 64 MiB

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 data

The input file contains an integer n (1n100).

Output data

Derive the output file the required number of telephone numbers.

Examples

Input example #1
1
Output example #1
8