D. Fibonacci Grouping
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

In a newly organized event, a group of $$$n$$$ individuals has lined up in a single row, numbered sequentially starting from one. To make the event more interesting, the participants are grouped based on a unique selection method. Each time a grouping occurs, individuals standing at positions that correspond to Fibonacci numbers are selected to form a group. The individuals selected in this round are then taken aside, while the remaining individuals are regrouped in a similar manner.

Your task is to find out how many distinct groups will be formed from the original lineup of $$$n$$$ individuals.

Input

The input consists of a single line containing an integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — the initial number of individuals.

Output

Output a single integer $$$k$$$ — the total number of groups created through this selection process.

Examples
Input
2
Output
1
Input
5
Output
2
Input
12
Output
3