FIBOBASE - Fibonacci Counting System

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


Added by:k[N]i[g]h[T]™
Date:2009-10-18
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 ERL NODEJS PERL6 VB.NET

hide comments
2020-02-29 15:00:09
Empty solution gets AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.