Given ** X**, compute the largest

**such that**

`N`**.**

`FIB(N) < X`Recall that:

`FIB(N) = FIB(N-1) + FIB(N-2) for N > 1``FIB(0) = 0``FIB(1) = 1`

### Input

The first line contains an integer ** X**.

### Output

A single integer ** N**.

### Constraints

`1 ≤ X ≤ 2`^{62}

### Samples

Input | Output |
---|---|

10 | 6 |

35 | 9 |

This problem is simple in theory, but the actual implementation makes it a bit trickier. Due to the constraints, some Fibonacci values may just barely exceed the maximum value that can be stored on a 64-bit numeric data type. The following implementation works as intended:

long long a = 0, b = 1; while(a < x - b) { long long c = a + b; a = b; b = c; ++n; }Whereas this very similar piece of code fails the test cases:

long long a = 0, b = 1; while(a + b < x) { long long c = a + b; a = b; b = c; ++n; }

This overflow problem can be avoided altogether by using a language which provides large numeric data types:

### Haskell implementation:

main = do input <- getContents let xs = map read (words $ last $ lines input) :: [Integer] putStrLn $ unwords $ map (show . solve) xs where solve x = length $ takeWhile (< x) fibos fibos = 1:1:zipWith (+) fibos (tail fibos)

### Python implementation:

#!/usr/bin/python3 n = int(input()) ans = [] for x in map(int, input().split()): fibos = [0, 1] while fibos[-1] < x: fibos.append(fibos[-1] + fibos[-2]) ans.append(len(fibos) - 2) print(" ".join(map(str, ans)))