DWITE, November 2012, Problem 3

A 'bitstring' is a string consisting of $0$s and $1$s. However, you're only looking for bitstrings with the following properties:

• There are no two consecutive $1$s in the bitstring.
• Every run of $0$s is of even length (i.e. every block of $0$s has an even number of $0$s in it).

$1001$ is an example of such a bitstring, but $10001$ is not. Luckily, your Computer Science (or Combinatorics) teacher shares a formula for figuring out how many such bitstrings exist for any given length $N$:

$${\displaystyle \begin{array}{rl}s(0)& =1\\ s(1)& =1\\ s(2)& =1\\ s(n)& =s(n-2)+s(n-3)\text{ for all }n>2\end{array}}$$

That is, there is only $1$ string of size $0$ (empty string matches both rules). Only $1$ string of size $1$ ("$1$"), and only $1$ string of size $2$ ("$00$"). For size $3$, you'd need to calculate the sum of $s(3-2)$ and $s(3-3)$, which are known from the results above.

The input will contain 5 test cases, each a line with a single integer $1\le N\le 75$, the length of the bitstring.

The output will contain 5 lines of output, each the number of different bitstrings of the corresponding length $N$, with the described properties.

Sample Input

1
20

Sample Output

1
200

Problem Resource: DWITE