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{align*} s(0) &= 1 \\ s(1) &= 1 \\ s(2) &= 1 \\ s(n) &= s(n-2) + s(n-3) \text{ for all } n > 2 \end{align*}$$

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