Islands

Time limit1sMemory limit1024 MB

Summary

Contestants disappear on islands following a Fibonacci-like rule, and we must find the island where the Nth contestant vanishes.

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

Problem

The 2020 International Olympiad in Informatics (IOI) will be held in Singapore, a country small in area but made up of many islands. On one of the IOI excursions, the $N$ contestants will visit these islands. But the contestants are busy thinking about how to implement Fibonacci heaps, so one by one they get lost and cannot find their way back.

On the first island, one contestant disappears, and on the second island another contestant disappears. On each island after that, as many contestants disappear as disappeared on the previous two islands combined (unless the contestants run out before then).

On which island does the last contestant disappear?

Input

The first line contains an integer $1\le N \le 10\,000$ , the number of contestants.

Output

Print an integer $A$ , the number of the island where the $N$ th contestant disappears.

Hint

Figure 1. The figure shows the situation in the first example, where the last (twelfth) contestant disappears on island 5.

Examples3

Example 1
Input
```
12
```
Expected output
```
5
```
Example 2
Input
```
13
```
Expected output
```
6
```
Example 3
Input
```
32
```
Expected output
```
7
```