The vassal of my vassal is not my vassal!#1411

The vassal of my vassal is not my vassal!

1 second
64 megabytes
Very easy

In every school of the Bandar-log, there is a strict hierarchy known as vassalage. Each Bandar-log, except the youngest, has one vassal, and everyone except the oldest has one patron (suzerain).

At the school named after P. Kaa, as in any other school, the Emperor of all the Bandar-log of the Jungle is held in high esteem. Several times a year, all schools participate in community service days to collect bananas, which are then presented as gifts to the Emperor. The size of these gifts significantly affects the Emperor's favor and the school's ranking.

The administration of the school named after P. Kaa learned that the students of the neighboring Bandar-log school named after M. Baloo collected a large number of bananas for the Emperor during the most recent community service day. Therefore, every Bandar-log at the school named after P. Kaa must collect as many bananas as their vassal collects, plus as many bananas as the vassal of their vassal collects. The two youngest Bandar-log are required to collect only one banana each.

Now the administration wants to know the minimum number of students their school must have in order to surpass the school named after M. Baloo in the rankings.

Input

The number of bananas (1 \leq n \leq 10^{1000}) collected by the Bandar-log of the school named after M. Baloo for the Emperor.

Output

Output the minimum number of students in the school named after P. Kaa needed to surpass the school named after M. Baloo in the rankings.

Examples

Example 1

Loading
Loading