eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

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

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

Input data

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

Output data

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

Examples

Input example #1
1
Output example #1
2
Source 2010 VII Открытый Чемпионат Харькова, I дивизион, 28 ноября, Задача I