EPIC1303 - Big Fibonacci

The Fibonacci sequence is defined as follows:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 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

Added by:BYU Admin
Date:2013-03-20
Time limit:2s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.