The Fibonacci sequence is defined as follows:

F_n = F_n-1 + F_n-2, where F₁ = 1 and F₂ = 1.

The first few terms are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

As you can see, the 7th term is the first one to have 2 digits and the 12th term is the first one to have 3 digits.  Without using a BigNum library, write a program that takes an integer as input and finds the index of the first term in the Fibonacci sequence to contain that many digits.

You will be using integers too large to store in 32-bits.  Do not use a BigNum library.

Input

An integer

Output

The index of the first number in the Fibonacci sequence to have the requested number of digits.

Example

Input:
3

Output:
12