##### DWITE, November 2012, Problem 3

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

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

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

- , ,
- for all

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

The input will contain 5 test cases, each a line with a single integer , the length of the bitstring.

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

#### Sample Input

```
1
20
```

#### Sample Output

```
1
200
```

## Comments