У кожній школі Бандар-логів існує сувора ієрархія, яку називають васалітетом. Кожен Бандар-лог, окрім наймолодшого, має одного васала, а кожен, окрім найстаршого, має одного покровителя (сюзерена).
У школі імені П. Ка́а, як і в будь-якій іншій школі, Імператор усіх Бандар-логів Джунглів користується великою повагою. Декілька разів на рік усі школи беруть участь у днях прибирання, під час яких збирають банани, що потім передаються Імператору як подарунок. Розмір цього подарунка суттєво впливає на прихильність Імператора та місце школи у рейтингу.
Адміністрації школи імені П. Ка́а стало відомо, що учні сусідньої школи Бандар-логів імені М. Ба́лу зібрали велику кількість бананів для Імператора під час останнього дня прибирання. Тому кожен Бандар-лог у школі імені П. Ка́а зобов’язаний зібрати стільки ж бананів, скільки збирає його васал, плюс стільки бананів, скільки збирає васал його васала. Двоє наймолодших Бандар-логів повинні зібрати лише по одному банану.
Тепер адміністрацію цікавить, яка найменша кількість учнів у їхній школі має бути, щоб перевершити школу імені М. Ба́лу у рейтингу.
Кількість бананів (1 \leq n \leq 10^{1000}), яку зібрали Бандар-логи школи імені М. Ба́лу для Імператора.
Виведіть мінімальну кількість учнів у школі імені П. Ка́а, необхідну для того, щоб перевершити школу імені М. Ба́лу у рейтингу.
Приклад 1