Fibonacci sequence is defined as follow: ~F_{1} = 1~, ~F_{2} = 2~, ~F_{i} = F_{i - 1} + F_{i - 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 = a_{1} \cdot F_{1} + a_{2}\cdot F_{2} + \dots~ Therefore, in Fibonacci system, ~X~ is known as: ~a_{n} a_{n - 1} \dots a_{1}~. For example, ~1 = 1_{F}~, ~2 = 10_{F}~, 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 \le N \le 10^{15})~

Output

Line ~1~: An integer ~K~ is the result

Sample Input

2

Sample Output

2