Sequence#3648

Sequence

1 second

128 megabytes

Easy

Consider the segment, at the ends of which 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$ 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

One positive integer $n$ ( $n \leq 1 0^{13}$ n \leq 10^{13}).

Output

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

Examples

Example 1

Loading

a + b

n \leq 1 0^{13}