Fibonacci System

Fibonacci 数列大家都知道了：

$$F_0=1,\quad F_1=1,\quad F_2=2,\quad F_3=3,\quad F_4=5,\quad F_5=8,\quad \dots$$

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

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

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

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

输入格式

一个数字 $N$。

输出格式

一行一个整数，表示前 $N$ 个位置出现了多少个 $1$。

样例输入

3

样例输出

2

样例解释

无限串的前 $3$ 个字符是 110，其中含有 $2$ 个 $1$。

数据范围

• $N\le 10^{15}$。

来源与许可

本题题面与测试数据整理自 BZOJ 2256。

样例 1

输入

3

输出

2