Tri Tiling

In how many ways can you tile a $3\times n$ rectangle with $2\times 1$ dominoes? Here is a sample tiling of a $3\times 12$ rectangle.

Input

Consists of several test cases followed by a line containing $-1$. Each test case is a line containing an integer $n(0\le n\le 30)$.

Output

For each test case print one integer giving the number of possible tilings.

Examples