Рассмотрим последовательность чисел 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). Каждый тест представляет собой строку, в которой записано целое число n (1 ≤ n ≤ 99 999). В последней строке входных данных записано число 0.

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