Fibonacci Base

Time limit1sMemory limit128 MB

Summary

Given N up to 10^15, count how many '1' characters appear among the first N characters of the string formed by concatenating Zeckendorf (Fibonacci base) representations of 1,2,3,... in order.

Level: Hard9 of 10
Topics: Math, Number theory, Binary search, Combinatorics
Solved: No attempts yet

Problem

The Fibonacci base is a way to represent every natural number uniquely using only the digits 0 and 1.

When a natural number $N$ is written in Fibonacci base as $N = \overline{a_n a_{n-1} \cdots a_1}_F$ , its value is $N = a_n F_n + a_{n-1} F_{n-1} + \cdots + a_1 F_1$ . Here $F_k$ is the Fibonacci sequence defined by $F_0 = F_1 = 1$ and $F_i = F_{i-1} + F_{i-2}$ . To make every representation unique, no two 1s may be adjacent in the Fibonacci base.

The following shows several natural numbers written in Fibonacci base.

$1 = 1_F, \quad 2 = 10_F, \quad 3 = 100_F, \quad 4 = 101_F, \quad 5 = 1000_F, \quad 6 = 1001_F, \quad 7 = 1010_F$

Now write the natural numbers $1, 2, 3, \cdots$ in Fibonacci base one after another, and concatenate all of the resulting strings. The beginning of the string built this way is 110100101100010011010 $\cdots$ .

Find how many 1s appear among the first $N$ characters of this string.

Input

The first line contains an integer $N$ . ( $0 \le N \le 10^{15}$ )

Output

Print the number of 1s among the first $N$ characters of the concatenated string.

Examples5

Example 1
Input
```
21
```
Expected output
```
10
```
Example 2
Input
```
0
```
Expected output
```
0
```
Example 3
Input
```
1
```
Expected output
```
1
```
Example 4
Input
```
2
```
Expected output
```
2
```
Example 5
Input
```
3
```
Expected output
```
2
```