Рассмотрим последовательность чисел a_i, i = 0, 1, 2, …, удовлетворяющих следующим условиям:

• a₀ = 0
• a₁ = 1
• a_2i = a_i
• a_{2i + 1} = a_i + a_{i + 1}

для каждого i = 1, 2, 3, … .

Напишите программу, которая для заданного значения n находит максимальное среди чисел a₀, a₁, …, a_n.

Входные данные состоят из нескольких тестов (не более 10 000). Каждый тест представляет собой строку, в которой записано целое число n (1 ≤ n < 10¹⁸). В последней строке входных данных записано число 0.

Для каждого n во вводе выведите соответствующее максимальное значение.

Задача совпадает с задачей 1079 “Максимум”, но имеет большие ограничения на входные данные.