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

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

1 секунда
64 мегабайти
Дуже легка

У кожній школі Бандар-логів існує сувора ієрархія, яку називають васалітетом. Кожен Бандар-лог, окрім наймолодшого, має одного васала, а кожен, окрім найстаршого, має одного покровителя (сюзерена).

У школі імені П. Ка́а, як і в будь-якій іншій школі, Імператор усіх Бандар-логів Джунглів користується великою повагою. Декілька разів на рік усі школи беруть участь у днях прибирання, під час яких збирають банани, що потім передаються Імператору як подарунок. Розмір цього подарунка суттєво впливає на прихильність Імператора та місце школи у рейтингу.

Адміністрації школи імені П. Ка́а стало відомо, що учні сусідньої школи Бандар-логів імені М. Ба́лу зібрали велику кількість бананів для Імператора під час останнього дня прибирання. Тому кожен Бандар-лог у школі імені П. Ка́а зобов’язаний зібрати стільки ж бананів, скільки збирає його васал, плюс стільки бананів, скільки збирає васал його васала. Двоє наймолодших Бандар-логів повинні зібрати лише по одному банану.

Тепер адміністрацію цікавить, яка найменша кількість учнів у їхній школі має бути, щоб перевершити школу імені М. Ба́лу у рейтингу.

Вхідні дані

Кількість бананів (1 \leq n \leq 10^{1000}), яку зібрали Бандар-логи школи імені М. Ба́лу для Імператора.

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading