/*
    题意：一个数可以写成Fibonacci数组成(整数的Fibonacci分解，是唯一的)，即
           N = anFn + an-1Fn-1 ++ a1F1        ai=0,1 （不会有相邻的1）
    1 = 1
    2 = 10
    3 = 100
    4 = 101
    
    现将所有的自然数的Fibonacci表示写成一串：110100101100010011010
    问前N个中1的个数 N <= 10^15
    F[0] = 1,F[1] = 1,F[2] = 2,F[3] = 3,F[4] = 5

    定义S[i]表示第i个Fibonacci之前的数的Fibonacci表示中1的个数之和
         B[i]表示第i个Fibonacci之前的数的位数之和
    递推式写一下几个数即可知道
    
    先二分查找出   B[i-1] < N <= B[i]
    然后得到最后的一个自然数是 (N-B[id-1])/id -1 + F[id];
    然后再统计下即可
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 70;

long long S[MAXN],F[MAXN],B[MAXN];
int n;

void init()
{
    S[1] = 1,F[0] = 1,B[1] = 1;
    F[1] = 1;
    for(int i=2;;i++)
    {
        S[i] = S[i-1] + S[i-2] + F[i-1];
        F[i] = F[i-1] + F[i-2];
        B[i] = B[i-1] + i*F[i-1];
        if(B[i] >= 1000000000000000LL){n= i;break;}
    }
}
int find(long long N)
{
    int low = 0,high = n;
    while(high-low>1)
    {
        int mid = (low + high )>>1;
        if(B[mid]>=N)high = mid;
        else low = mid;
    }
    return high;
}
long long solve(long long N,int id)
{
    long long num = (N-B[id-1])/id -1 + F[id];
    int r = (N-B[id-1])%id;

    long long ans = 0, x= num+1;
    int i = id;
    while(num>0)
    {
        if(num>=F[i])//有点类似数位类统计的逐位确定
        {
            ans += (num-F[i]+1)+S[i-1];
            num-=F[i];
        }
        i--;
    }
    i = id;
    while(r && x>0)
    {
        if(x>=F[i])ans++,x-=F[i];
        r--;
        i--;
    }    
    return ans;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in","r",stdin);
#endif

    init();
    long long N;
    while(scanf("%lld",&N)!=EOF)
    {
        if(N == 0){puts("0");continue;}
        printf("%lld\n",solve(N,find(N)));
    }
    return 0;
}