Some sequences of bits (1) P81826

Write a program that prints the number of sequences of length $n$ made up of only zeros and ones that do not contain two consecutive zeros nor three consecutive ones.

For instance, there are 7 sequences for $n = 5$: $$01010 \quad 01011 \quad 01101 \quad 10101 \quad 10110 \quad 11010 \quad 11011$$

Input

Input consists of several natural numbers $n$, each between 0 and 150.

Output

For every $n$, print the required number.