Fibonacci sequence is defined as follow: F₁ = 1, F₂ = 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₁xF₁ + a₂xF₂ + … Therefore, in Fibonacci system, X is known as: a_na_n-1…a₁. 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 <= N <= 10¹⁵)

Output

Line 1: An integer K is the result

Example

Input:
2

Output:
2