Hexagonal Tiles

Mary's route to school is a straight strip paved with hexagonal tiles.

The tiles are laid out in an offset, brick-like pattern, so every tile shares an edge with the two tiles that come immediately after it. At the very front of the strip there is a special tile marked with a smiling face; the remaining tiles are numbered $1, 2, 3, \dots$ consecutively in ascending order.

On her way to school Mary steps from tile to tile following these rules:

• She always starts on the smiling-face tile, which sits before tile $1$ and touches both tile $1$ and tile $2$.
• She may never step onto a tile whose number is smaller than the tile she is standing on, so the numbers she steps on strictly increase.
• Each step must go to a neighboring tile. Because of the layout, from the tile numbered $k$ she can move forward only to tile $k+1$ or tile $k+2$.
• She must finish on the highest-numbered tile.

A step sequence is the ordered list of numbered tiles she steps on. Mary never wants to repeat a sequence, and she wonders: for a strip with $N$ numbered tiles (plus the smiling-face tile), how many days would it take to walk every possible sequence exactly once, one sequence per day?

For instance, with $N = 4$ tiles there are five possible sequences: 1-2-3-4, 1-2-4, 1-3-4, 2-3-4, and 2-4.

Given $N$, determine how many different step sequences exist.

The input consists of several test cases. Each test case is a single line containing one integer $N$ ($1 \le N \le 40$), the number of numbered tiles on the strip.

The list of test cases ends with a line containing a single $0$, which must not be processed.

For each test case, print a single line containing one integer: the number of different step sequences for a strip with $N$ numbered tiles.