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

## 1396. Maximum. Version 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Consider the sequence of numbers a[i], i = 0, 1, 2, ..., which satisfies the following requirments:
``` 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 (0 < N < 1018) finds the largest number among the numbers a, a, ..., a[N].

### Исходные данные

Input contains not more than 10000 lines containing one number N. The last line contains 0.

### Результат

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

### Пример

исходные данныерезультат
```5
10
0
```
```3
4
```

### Замечания

This problem is the same as “Maximum” but with bigger limitations.
Автор задачи: Prepared by Vladimir Yakovlev
Метки: нет