/*
    題意：一個數可以寫成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;
}