Consider the sequence of numbers a_i, i = 0, 1, 2, …, which satisfies the following requirements:

• a₀ = 0
• a₁ = 1
• a_2i = a_i
• a_2i+1 = a_i + a_i+1

for every i = 1, 2, 3, … .

Write a program which for a given value of n finds the largest number among the numbers a₀, a₁, …,a_n.

You are given several test cases (not more than 10). Each test case is a line containing an integern (1 ≤ n ≤ 99 999). The last line of input contains 0.

For every n in the input write the corresponding maximum value found.

// Ural Problem 1079. Maximum

// Verdict: Accepted

// Submission Date: 14:33:08 15 Jan 2014

// Run Time: 0.031s

//

// 版权所有（C）acutus   (mail: acutus@126.com)

// 博客地址：http://www.cnblogs.com/acutus/// [解题方法]

// 简单题模拟题

// 注意：最大项有可能是奇数项

#include<stdio.h>

long long a[], b[];

void solve()

{

    int i, j, max, n;

    a[] = b[] = ;

    a[] = b[] = ;

    max = ;

    for(i = ; i < ; i++) {

        if(i % ) {

            j = (i - ) >> ;

            a[i] = a[j] + a[j + ];

        } else {

            a[i] = a[i >> ];

        }

        if(a[i] > max)

            max = a[i];

        b[i] = max;

    }

    while(scanf("%d", &n) && n) {

        printf("%lld\n", b[n]);

    }

}

int main()

{

    solve();

    return ;

}