Author:  ACM ICPC NEERC 2008 Jury  Time limit:  2 sec  
Input file:  fibonacci.in  Memory limit:  256 Mb  
Output file:  fibonacci.out 
Author: Anton Maydell Text: Andrew Lopatin Tests: Anton Maydell
Little John studies numeral systems. After learning all about fixedbase 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 \t{1}s in adjacent positions.
One can prove that if you have number N = a_{n} a_{n − 1}… a_{1}_{F} in Fibonacci system, its value is equal to N = a_{n} ⋅ F_{n} + a_{n − 1} ⋅ F_{n − 1} + … + a_{1} ⋅ F_{1}, where F_{k} is a usual Fibonacci sequence defined by F_{0} = F_{1} = 1, F_{i} = F_{i − 1} + F_{i − 2}.
For example, first few natural numbers have the following unique representations in Fibonacci system:
1 = 1_{F}, 2 = 10_{F}, 3 = 100_{F}, 4 = 101_{F}, 5 = 1000_{F}, 6 = 1001_{F}, 7 = 1010_{F},
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 \t{1} occurs in the Nth prefix of the string. Remember that the Nth 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 Nth 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 Nth prefix of John's string.
No.  Input file (fibonacci.in ) 
Output file (fibonacci.out ) 

1 

