Tile Decoration

Interview

Time limit2sMemory limit512 MB

Summary

Given N, compute the perimeter of the rectangle formed by N spiral tiles whose side lengths follow the Fibonacci sequence, starting at 1, 1, 2, 3, 5, 8.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

A tile decoration in a park is made of square tiles glued together in a spiral, like the shell of a nautilus. It starts with a tile of side 1, and every tile added further out is larger. Part of the decoration looks like this.

The number written on a tile is the length of its side. Reading the side lengths from the innermost tile outward gives 1, 1, 2, 3, 5, 8, ... . From the third tile on, the side length of a tile is the sum of the side lengths of the two tiles before it.

Gluing $N$ tiles together by this rule always produces a single rectangle. For example, the rectangle formed by the first five tiles (drawn in red in the picture) has perimeter 26.

Given the number of tiles $N$ , write a program that computes the perimeter of the rectangle formed by those $N$ tiles.

Input

The first line contains an integer $N$ , the number of tiles. ( $1 \le N \le 80$ )

Output

Print the perimeter of the rectangle formed by the $N$ tiles on the first line.

The answer can exceed the 32-bit integer range, so use a 64-bit integer type.

Examples2

Example 1
Input
```
5
```
Expected output
```
26
```
Example 2
Input
```
6
```
Expected output
```
42
```