题目描述

Fib数列，大家都知道了。

$F_0 = 1$
$F_1 = 1$
$F_2 = 2$
$F_3 = 3$
$F_4 = 5$
$F_5 = 8$

现在我们将十进制的数，转成Fib进制，对于 $1$ 到 $7$ 可以分成下面形式：

$1 = 1_F$
$2 = 10_F$
$3 = 100_F$
$4 = 101_F$
$5 = 1000_F$
$6 = 1001_F$
$7 = 1010_F$
$8 = 10000_F$

现在我们将转化出来的 $1$ 和 $0$ 构成的串，连在一起，对于上面数字 $1$ 到 $7$ 就成了 $\text{110100101100010011010}\dots$

对于这样一个无限长的字符串，问前 $n$ 个字符中有多少个 $1$。

输入格式

一个数字 $n$。

输出格式

前 $n$ 个位置出现了多少个 $1$。

3

2

数据规模与约定

$100\%$ 的数据满足：$n \le 1 \times 10^{15}$。