Maximum

#include <bits/stdc++.h>
using namespace std;

int main(){
    int long long i, n, k = 99999;

    int long long arr[k];

    k /= 2;
    arr[0] = 0;
    arr[1] = 1;

    for(i = 1; i <= k; i++){
        arr[2 * i] = arr[i];
        arr[2 * i + 1] = arr[i] + arr[i + 1];
    }
    //cout << arr[(2 * i) + 1] << endl;

    while(1){
        scanf("%lld", &n);

        if(n == 0) break;

        if(n % 2 == 0){
            printf("%lld\n", arr[n - 1]);
        } else {
            printf("%lld\n", arr[n]);
        }
    }

    return 0;
}