SM is specially passionate to represent integers in different counting systems. 
This time, SM spent a lot of time for the Fibonacci Binary counting system.
Features of this system is that there aren’t  two digits 1 standing side by side. 
An integer M can be expressed as
M10 = anan-1…a2a1F ;  
which ai = 1 or 0, ai*ai-1 = 0 and M = anFn + an-1Fn-1 + … + a2F2 + a1F1; 
which F0 = F1 = 1, Fi = Fi-1 + Fi-2.
Example:
110 = 1F
210 = 10F
310 = 100F
410 = 101F
510 = 1000F
610 = 1001F
710 = 1010F
SM continously wrote natural numbers 1, 2, 3… in  the Fibonacci Binary counting system 
and got a infinite string containing 0, 1. The beginning of the string is 110100101100010011010…
Looking at his result, SM wondered how many digits 1 in the first N digits of the sequence ?
Input
An integer N (0 <= N <= 1015).
Output
Result in integer.
Example
Input:
21

Output:
10