UVA1652 Fibonacci System

Little John 正在研究数位系统。在学习完所有关于固定基数的系统后，他对更为不同寻常的情况产生了兴趣。在这些情况中，他发现了一种 Fibonacci 数位系统，该系统仅使用两个数码：零和一，就能唯一地表示所有自然数。但与常见的二进制记数法不同，在 Fibonacci 数位系统中不允许有相邻的两个 $\tt 1$。 可以证明，如果在 Fibonacci 系统中有一个数 $N = \overline{a _ n a_{n - 1} \dots a _ 1} _ F$，那么它的数值等于 $N = a_n \cdot F_n + a_{n-1} \cdot F_{n-1} + \dots + a_1 \cdot F_1$, 其中 $F_k$ 是通常定义的 Fibonacci 数列，满足 $F_0 = F_1 = 1, F_i = F_{i-1} + F_{i-2}$。 例如，前几个自然数在 Fibonacci 数位系统中的唯一表示如下： $$\begin{aligned}1 &= 1 _ F \\ 2 &= 10 _ F \\ 3 &= 100 _ F \\ 4 &= 101 _ F \\ 5 &= 1000 _ F \\ 6 &= 1001 _ F \\ 7 &= 1010 _ F\end{aligned}$$ John 写了一个非常长的字符串（可视为无限长），它由 Fibonacci 数位系统中每个自然数的表示连接组成。例如，该字符串的前几位数字是 $\tt 110100101100010011010$。 他非常想知道，在该字符串的第 $N$ 个前缀中，数字 $\tt 1$ 出现了多少次。这里第 $N$ 个前缀就是这个字符串的前 $N$ 位。 编写一个程序用来确定 John 的字符串第 $N$ 个前缀中数字 $\tt 1$ 出现的次数。

输入文件包含若干个测试用例，每个测试用例的格式如下： 输入包含一个整数 $N$（$0 \le N \le 10 ^ {15}$）。

对于每个测试用例，在单独的一行上输出一个整数表示 John 的字符串第 $N$ 个前缀中 $\tt 1$ 出现的次数。