java

Максимум
Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ
Рассмотрим последовательность чисел ai, i = 0, 1, 2, …, удовлетворяющих следующим условиям:

a0 = 0
a1 = 1
a2i = ai
a2i + 1 = ai + ai + 1

для каждого i = 1, 2, 3, … .
Напишите программу, которая для заданного значения n находит максимальное среди чисел a0, a1, …, an.
Исходные данные
Входные данные состоят из нескольких тестов (не более 10). Каждый тест представляет собой строку, в которой записано целое число n (1 ≤ n ≤ 99 999). В последней строке входных данных записано число 0.
Результат
Для каждого n во вводе выведите соответствующее максимальное значение.