Problems
Sequence
Sequence
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
we get
Then we get the segment
and so on till infinity. How many times the positive integer n will be written on a segment?
Input data
One positive integer n (n ≤ 10^13
).
Output data
The number of times the number n appears on a segment.
Examples
Input example #1
4
Output example #1
2