ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1079. Максимум

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим последовательность чисел 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 во вводе выведите соответствующее максимальное значение.

Пример

исходные данныерезультат
5
10
0
3
4
Автор задачи: Emil Kelevedzhiev
Источник задачи: Winter Mathematical Festival Varna '2001 Informatics Tournament