В каждой школе бандерлогов есть очень строгая иерархия -- вассалитет. У каждого бандерлога, кроме самого младшего есть один вассал и соответственно у всех кроме самого старшего есть один покровитель -- сюзерен. В школе им. П. Каа, как и в любой другой школе, очень чтят Императора всех бандерлогов Джунглей. Несколько раз в год во всех школах даже проходят субботники по сбору бананов, которые преподносятся в дар Императору. От размеров подарков очень сильно зависит благосклонность Императора и рейтинг школы. Администрации школы им. П. Каа стало известно, что учащиеся соседней школы бандерлогов им. М. Балу на последнем субботнике собрали для Императора очень, очень много бананов, и, поэтому, каждый бандерлог школы им. П. Каа должен собрать для Императора столько бананов, сколько бананов соберёт его вассал плюс столько бананов, сколько соберёт вассал его вассала. Два самых младших бандерлога должны собрать всего лишь по одному банану. Теперь администрацию терзает вопрос, какое же наименьшее количество учеников должно быть в их школе, чтобы обойти в рейтинге школу им. М. Балу. \InputFile Количество бананов \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^1000}), собранных для Императора бандерлогами школы им. М. Балу. \OutputFile Вывести минимальное количество учеников в школе им. П. Каа, необходимое для того, чтобы обойти в рейтинге школу им. М. Балу.