**1 人解决**，8 人已尝试。

**1 份提交通过**，共有 31 份提交。

**9.9** EMB 奖励。

**单点时限: **5.0 sec

**内存限制: **256 MB

Little John studies numeral systems. After learning all about fixed-base systems, he became interested in more unusual cases. Among those cases he found a Fibonacci system, which represents all natural numbers in an unique way using only two digits: zero and one. But unlike usual binary scale of notation, in the Fibonacci system you are not allowed to place two 1s in adjacent positions.

John wrote a very long string (consider it infinite) consisting of consecutive representations of natural numbers in Fibonacci system. For example, the first few digits of this string are 110100101100010011010. . .

He is very interested, how many times the digit 1 occurs in the N-th prefix of the string. Remember that the N-th prefix of the string is just a string consisting of its first N characters.

Write a program which determines how many times the digit 1 occurs in N-th prefix of John’s string.

The input file contains a single integer N (0<N<10^15).

Output a single integer ― the number of 1s in N-th prefix of John’s string.

Input

21

Output

10

**1 人解决**，8 人已尝试。

**1 份提交通过**，共有 31 份提交。

**9.9** EMB 奖励。

题目标签