Consider the sequence of numbers

*a*_{i},

*i* = 0, 1, 2, …, which satisfies the following requirements:

*a*_{0} = 0
*a*_{1} = 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*_{0}, *a*_{1}, …, *a*_{n}.

### Input

You are given several test cases (not more than 10 000). Each test case is a line containing an integer *n* (1 ≤ *n* < 10^{18}).
The last line of input contains 0.

### Output

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

### Sample

### Notes

This problem is the same as 1079 “

Maximum” but with bigger limitations.

**Problem Author: **Prepared by Vladimir Yakovlev