eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Вассал моего вассала – не мой вассал!

Вассал моего вассала – не мой вассал!

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В каждой школе бандерлогов есть очень строгая иерархия – вассалитет. У каждого бандерлога, кроме самого младшего есть один вассал и соответственно у всех кроме самого старшего есть один покровитель – сюзерен.

В школе им. П. Каа, как и в любой другой школе, очень чтят Императора всех бандерлогов Джунглей. Несколько раз в год во всех школах даже проходят субботники по сбору бананов, которые преподносятся в дар Императору. От размеров подарков очень сильно зависит благосклонность Императора и рейтинг школы.

Администрации школы им. П. Каа стало известно, что учащиеся соседней школы бандерлогов им. М. Балу на последнем субботнике собрали для Императора очень, очень много бананов, и, поэтому, каждый бандерлог школы им. П. Каа должен собрать для Императора столько бананов, сколько бананов соберёт его вассал плюс столько бананов, сколько соберёт вассал его вассала. Два самых младших бандерлога должны собрать всего лишь по одному банану.

Теперь администрацию терзает вопрос, какое же наименьшее количество учеников должно быть в их школе, чтобы обойти в рейтинге школу им. М. Балу.

Входные данные

Количество бананов n (1 n 10^1000), собранных для Императора бандерлогами школы им. М. Балу.

Выходные данные

Вывести минимальное количество учеников в школе им. П. Каа, необходимое для того, чтобы обойти в рейтинге школу им. М. Балу.

Пример

Входные данные #1
1
Выходные данные #1
2
Источник 2010 VII Открытый Чемпионат Харькова, I дивизион, 28 ноября, Задача I