Description

Fib数列，大家都知道了.
F[0]=1
F[1]=1
F[2]=2
F[3]=3
F[4]=5
F[5]=8
现在我们将十进制的数，转成Fib进制，对于1到7可以分成下面形式
1=1F
2=10F
3=100F
4=101F
5=1000F
6=1001F
7=1010F
8=10000F
现在我们将转化出来的1和0构成的串，连在一起，对于上面数字1到7就成了110100101100010011010...
对于这样一个无限长的字符串，问前N个字符中有多少个1

Input

一个数字N，N < = 10^15

Output

前N个位置出现了多少个1

Sample Input

Sample Output

Hint

Source