eolymp
bolt
Try our new interface for solving problems
Problems

Sequence

Sequence

Time limit 1 second
Memory limit 128 MiB

Consider the segment, at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends a and b (inside which the numbers are absent) we shall write in the middle the number a + b. So from the starting segment

prb3648-01

we get

prb3648-02

Then we get the segment

prb3648-03

and so on till infinity. How many times the positive integer n will be written on a segment?

Input data

One positive integer n (n10^13).

Output data

The number of times the number n appears on a segment.

Examples

Input example #1
4
Output example #1
2
Source III International Summer School Programming in Sevastopol 2012