Computer Transformation

Time limit1sMemory limit128 MB

Summary

Given n up to 1000, compute the count of adjacent

Level: Medium6 of 10
Topics: Math, String, Dynamic programming
Solved: No attempts yet

Problem

A computer starts with a sequence consisting of a single digit: the number $1$ . At each time step, the computer simultaneously replaces every digit $0$ with the sequence $1\,0$ and every digit $1$ with the sequence $0\,1$ .

Thus after the first step the sequence is $0\,1$ ; after the second step it is $1\,0\,0\,1$ ; after the third step it is $0\,1\,1\,0\,1\,0\,0\,1$ ; and so on.

How many pairs of consecutive zeroes appear in the sequence after $n$ steps?

Input

Each input line contains one natural number $n$ ( $0 < n \le 1000$ ). Process every line until the end of input.

Output

For each $n$ , print on its own line the number of pairs of consecutive zeroes in the sequence after $n$ steps.

Examples3

Example 1
Input
```
2
3
```
Expected output
```
1
1
```
Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
4
5
6
```
Expected output
```
3
5
11
```