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 000). Each test case is a line containing an integer n (1 ≤ n < 10¹⁸). The last line of input contains 0.

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

This problem is the same as 1079 “Maximum” but with bigger limitations.