A lot of phones nowadays are moving away from the standard number lock to using pattern locks. Given a 3-by-3 grid of dots, a pattern is defined to be a directed path among the 9 points of length at least 1. (Note: A path visits each point at most once.) However, there’s an extra condition: The path can’t cross an unvisited vertex (e.g. you can’t go from the top-left dot to the bottom-right dot unless the center dot has already been visited). For example, the following picture depicts one possible pattern for a 3-by-3 grid:

One day you decide to find out exactly how secure this lock is by determining the number of possible patterns you can make for a 3-by-3 grid of up to a particular length.

The input file **DATA5.txt** will contain 5 test cases. The first line of each test case contains a number `N` (1 ≤ `N` ≤ 8) representing the maximum length the pattern can be.

The output file **OUT5.txt** will contain 5 lines. Each line is an integer representing the total possible number of patterns you can have for the 3-by-3 grid lock, up to the length given by the input.

```
1
2
```

```
56
376
```