SPFIBO - Fibonacci Sequence

no tags 

Fibonacci sequence is defined as follow: F1 = 1, F2 = 2, Fi = Fi-1 + Fi-2 (i > 2).

Each natural number X can be expressed by the maximum numbers that are less than or equal to X in Fibonacci sequence: X = a1xF1 + a2xF2 + … Therefore, in Fibonacci system, X is known as: anan-1…a1. For example, 1 = 1F, 2 = 10F, etc. If we write all natural numbers successively in Fibonacci system, we will obtain a sequence like this: 1_1_0… This is called “Fibonacci bit sequence of natural numbers”.

Your task is counting the numbers of times that bit 1 appears in the first N bits of this sequence.

Input

Line 1: An integer N (1 <= N <= 1015)

Output

Line 1: An integer K is the result

Example

Input:
2

Output:
2


Added by:HNUE
Date:2010-11-16
Time limit:0.102s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Anh Hiếu