Famous Brazil city Rio de Janeiro holds a tennis tournament and Ostap Bender doesn't want to miss this event. There will be n players participating, and the tournament will follow knockout rules from the very first game. That means, that if someone loses a game he leaves the tournament immediately.

Organizers are still arranging tournament grid (i.e. the order games will happen and who is going to play with whom) but they have already fixed one rule: two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played. Of course, both players had to win all their games in order to continue participating in the tournament.

Tournament hasn't started yet so the audience is a bit bored. Ostap decided to find out what is the maximum number of games the winner of the tournament can take part in (assuming the rule above is used). However, it is unlikely he can deal with this problem without your help.


-----Input-----

The only line of the input contains a single integer n (2 ≤ n ≤ 10^18) — the number of players to participate in the tournament.


-----Output-----

Print the maximum number of games in which the winner of the tournament can take part.


-----Examples-----
Input
2

Output
1

Input
3

Output
2

Input
4

Output
2

Input
10

Output
4



-----Note-----

In all samples we consider that player number 1 is the winner.

In the first sample, there would be only one game so the answer is 1.

In the second sample, player 1 can consequently beat players 2 and 3. 

In the third sample, player 1 can't play with each other player as after he plays with players 2 and 3 he can't play against player 4, as he has 0 games played, while player 1 already played 2. Thus, the answer is 2 and to achieve we make pairs (1, 2) and (3, 4) and then clash the winners.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
x = 0
cur = 1
lst = 1
while cur + lst <= n:
    cur, lst = cur + lst, cur
    x += 1
print(x)


n=int(input())
a,b=1,1
ans=0
while b<=n:
    a,b=b,a+b
    ans+=1
print(ans-1)


from math import *
from sys import *
from queue import *
from decimal import *

n=int(input())
f2=1
f3=2
i=0
while f3<=n:
  i+=1
  f2,f3=f3,f2+f3
print(i)  

n = int(input())
prev, cur = 1, 2
iters = 0
while (cur < n):
    prev, cur = cur, cur + prev
    iters += 1
ans = iters + bool(cur == n)
print(ans)

def solve(n):
    k = 0
    f1, f2 = 1, 2
    while not f1 <= n < f2:
        k += 1
        t = f1
        f1 = f2
        f2 = f1 + t
    return k

n = int(input())
print(solve(n))


n = int(input())

dp = {1: 2, 2: 3}

def cost(i):
    if i not in dp:
        dp[i] = cost(i-1) + cost(i-2)
    return dp[i]

ans = 1

while cost(ans) <= n:
    ans += 1

print(ans-1)


# You lost the game.

n = int(input())

T = {}


T[1] = 2
T[2] = 3
T[3] = 5
T[4] = 8

t = 1
r = 0
while r < 4 and t <= n:
    r += 1
    t = T[r]
    
while t <= n:
    r += 1
    t += T[r-2]
    T[r] = t
    
print(r-1)


from sys import stdin
from sys import stdout
n = int(stdin.readline().strip())

m = 1
a = 1
b = 2
while b < n:
    m += 1
    a, b = b, a+b
if b > n:
    m -= 1
stdout.write(str(m))


a = int(input())
fib=[1,2]
for i in range(100):
    fib.append(fib[-1]+fib[-2])

for i in range(1, 1000):
    if fib[i]<=a<fib[i+1]:
        print(i)
        quit()

n=int(input())
if n==2:
    print(1)
else:
    ans=3
    oldans=2
    count=2
    b=0
    while ans<=n:
        if ans==n:
            b=1
            print(count)
            break
        else:
            oldans,ans=ans,ans+oldans
            count+=1
    if b==0:
        print(count-1)
        
            


n = int(input())

l = []
l.append(0)
l.append(1)
l.append(2)

k = 2
m = 1

while k < n:
    k = k + l[m]
    m = m + 1
    l.append(k)
    
if k > n:
    m = m - 1

print(m)

n = int(input())
fib = [1, 2]
for i in range(2, 10000):
    fib.append(fib[i - 1] + fib[i - 2])
l = 0
r = 10000
while (r - l > 1):
    mid = (r + l) // 2
    if (fib[mid] > n):
        r = mid
    else:
        l = mid
print(l)

def h(z):
  a = 0
  b = 1
  res = 1
  while True:
    a, b = b, a + b + 1
    if b >= z:
      break
    res += 1  
  return res
  
n = int(input())
print(h(n))  

n = int(input())
games = n - 1
massiv = [2]
while massiv[-1] <= games:
    if len(massiv) == 1:
        massiv += [4]
    else:    
        massiv += [massiv[-1] + massiv[-2] + 1]
print(len(massiv))    

from math import *

def main():
    n=int(input())
    prev,fib=1,2
    count=0
    while fib<=n:
        prev,fib=fib,prev+fib
        count+=1
    print(count)
    
main()


def cost(nk):
    
    ns = max(0, k - 1)
    if ns > n - 2:
        return 0
    
    return f(n - ns - 1, k + 1) + 1


n = int(input())
F = [0] * 100
F[0] = 1
F[1] = 2
ans = 1

for i in range(2, 100):
    F[i] = F[i - 1] + F[i - 2]
    if F[i] <= n:
        ans = i
        
print(ans)

n = int(input())

if n == 2:
	print(1)
elif n == 3:
	print(2)
else:
	x = 2
	y = 3
	counter = 0
	while x+ y <= n:
		x, y = y, x+y
		counter += 1
	print(2+counter)

n = int(input())
f = [1, 1]
while f[-1] < n:
	f += [f[-1] + f[-2]]
if f[-1] == n:
	print(len(f) - 2)
else:
	print(len(f) - 3)

n = int(input())

lst1 = 1
lst2 = 1

cnt = 0

while (True):
    cnt += 1
    lst1, lst2 = lst2, lst1
    if (lst1 + lst2 == n):
        print(cnt)
        return
    if (lst1 + lst2 > n):
        print(cnt - 1)
        return
    lst2 = lst1 + lst2

n = int(input())
f = []
ans = 1
f.append(1)
f.append(2)
while f[ans] < n:
    f.append(f[ans] + f[ans - 1])
    ans += 1
if f[ans] == n:
    print(ans)
else:
    print(ans - 1)

a = []
a.append(1)
a.append(1)
n = int(input())
if (n == 2):
    print(1)
    return
i = 2
while(1):
    a.append(a[i - 1] + a[i - 2])
    if (a[i] >= n):
        print(i - 2 + int(a[i] == n))
        break
    i += 1

import math,sys,re,itertools,pprint,collections,copy
rs,ri,rai,raf=input,lambda:int(input()),lambda:list(map(int, input().split())),lambda:list(map(float, input().split()))

t = [2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049,
12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717,
365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,
10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994,
190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050,
3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685,
37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585,
420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120,
4660046610375530309, 7540113804746346429]

n = ri()

for i in range(len(t)):
    if n < t[i]:
        print(i)
        break


n = int(input())

f = 2
g = 1
c = 0

while f <= n:
	f, g = f+g, f
	c += 1

print(c)

def tennis(n):
    u,v = 1,2
    j = 1
    while v <= n:
        u,v = v, u+v
        j += 1
    return j-1

print(tennis(int(input())))


fmap = lambda f, l: list(map(f, l))
parse_int = lambda: fmap(int, input().split())

DEBUG = False#True#


n = int(input())

cost_of = [0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 701408732, 1134903169, 1836311902, 2971215072, 4807526975, 7778742048, 12586269024, 20365011073, 32951280098, 53316291172, 86267571271, 139583862444, 225851433716, 365435296161, 591286729878, 956722026040, 1548008755919, 2504730781960, 4052739537880, 6557470319841, 10610209857722, 17167680177564, 27777890035287, 44945570212852, 72723460248140, 117669030460993, 190392490709134, 308061521170128, 498454011879263, 806515533049392, 1304969544928656, 2111485077978049, 3416454622906706, 5527939700884756, 8944394323791463, 14472334024676220, 23416728348467684, 37889062373143905, 61305790721611590, 99194853094755496, 160500643816367087, 259695496911122584, 420196140727489672, 679891637638612257, 1100087778366101930, 1779979416004714188]

for i in range(len(cost_of)):
    if cost_of[i]>n-1: break
print(i-1)