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: MEDIUM_HARD
Tags: Constructive algorithms

Combinatorics

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
f = 2
g = 1
c = 0
while f <= n:
	(f, g) = (f + g, f)
	c += 1
print(c)


(n, arr, i) = (int(input()), [2, 3], 1)
if n == 2:
	print(1)
elif n == 3:
	print(2)
else:
	(a, ans) = (arr[i] + arr[i - 1], 2)
	while a <= n:
		i += 1
		arr.append(a)
		a = arr[i] + arr[i - 1]
		ans += 1
	print(ans)


n = int(input())
arr = [1, 2]
while True:
	tmp = arr[-1] + arr[-2]
	if tmp > n:
		break
	arr.append(tmp)
print(len(arr) - 1)


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


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


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


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)


import io
import os
players = int(input())
to_win_n_games = [1, 2]
n = 1
while to_win_n_games[n] <= players:
	to_win_n_games.append(to_win_n_games[n] + to_win_n_games[n - 1])
	n += 1
print(n - 1)


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()


n = int(input())
a = [0 for i in range(1000)]
a[1] = 2
a[2] = 3
if n < 4:
	print(n - 1)
	exit()
i = 3
while True:
	a[i] = a[i - 1] + a[i - 2]
	if a[i] > n:
		print(i - 1)
		exit()
	i += 1


from math import *
n = int(input())
(a, b) = (2, 3)
c = 0
while n >= a:
	(a, b) = (b, a + b)
	c += 1
print(c)


import math as mt
import sys, string
input = sys.stdin.readline
from collections import defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
n = I()
l = [1, 2]
for i in range(1000):
	l.append(l[-1] + l[-2])
ans = 0
for i in range(len(l)):
	if n < l[i]:
		break
	ans = i
print(ans)


def solucion():
	n = int(input())
	minDJugadores = [2, 3]
	if 2 <= n <= 3:
		if n == 2:
			print('1')
		else:
			print('2')
	else:
		while n >= minDJugadores[len(minDJugadores) - 1]:
			minDJugadores.append(minDJugadores[len(minDJugadores) - 1] + minDJugadores[len(minDJugadores) - 2])
		print(len(minDJugadores) - 1)
solucion()


n = int(input())
if n <= 2:
	print(1)
	exit(0)
F = [1, 1]
while F[-1] < n:
	F.append(F[-1] + F[-2])
s = 0
for i in range(len(F)):
	s += F[i]
	if s >= n:
		print(i)
		break


fmap = lambda f, l: list(map(f, l))
parse_int = lambda : fmap(int, input().split())
DEBUG = False
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)


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))


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


fibo = [1, 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, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176, 1500520536206896083277]
n = int(input())
for i in range(len(fibo)):
	if fibo[i] > n:
		print(i - 1)
		break


fib = [1, 2]
for i in range(90):
	fib.append(fib[-1] + fib[-2])
n = int(input())
for i in range(len(fib)):
	if fib[i] > n:
		print(i - 1)
		break


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	(a, b, z, c) = (0, 1, 1, 1)
	while c < n:
		(a, b) = (b, c)
		c = a + b
		z += 1
	print(z - 1 - (c != n))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def getLnInput():
	return input().split()

def main(n):
	current = 1
	prev = 1
	term = -1
	while current <= n:
		(current, prev) = (current + prev, current)
		term += 1
	print(term)
	return
main(int(getLnInput()[0]))


import bisect
n = int(input())
c = [1, 2]
for i in range(100):
	c.append(c[-1] + c[-2])
if n in c:
	print(bisect.bisect_left(c, n))
else:
	print(bisect.bisect_left(c, n) - 1)


n = int(input())
dp = [0 for i in range(200001)]
dp[0] = 1
dp[1] = 2
i = 1
while dp[i] <= n:
	i += 1
	dp[i] = dp[i - 1] + dp[i - 2]
print(i - 1)


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())
fib = 1
last = 1
i = 0
while True:
	i += 1
	fib = fib + last
	last = fib - last
	if fib > n:
		print(i - 1)
		exit(0)


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


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)


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


def games(m):
	lst = [2]
	while lst[-1] <= m - 1:
		if len(lst) == 1:
			lst += [4]
		else:
			lst += [lst[-1] + lst[-2] + 1]
	return len(lst)
print(games(int(input())))


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


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)


n = int(input())
n -= 2
sc = 1
first = True
f1 = 1
f2 = 1
f3 = 2
while n > 0:
	if first:
		first = False
		n -= 1
		sc += 1
	else:
		n -= f3
		sc += 1
		f1 = f2
		f2 = f3
		f3 = f1 + f2
if n < 0:
	sc -= 1
print(sc)


n = int(input())
total = 0
a = 1
b = 2
c = 0
cont = 0
while c <= n:
	c = a + b
	a = b
	b = c
	cont += 1
print(cont)


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)


import bisect as b, itertools as i
f = [1] * 2
for I in range(2, 100):
	f += [f[I - 1] + f[I - 2]]
print(b.bisect_left(list(i.accumulate(f)), int(input())))


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))


import math

def main():
	n = int(input())
	phib = [1, 1]
	ans = 0
	while phib[-1] + phib[-2] <= n:
		phib.append(phib[-1] + phib[-2])
		ans += 1
	print(ans)
main()


n = int(input())
if n == 2:
	print(1)
	exit()
p = 2
pp = 1
i = 1
while True:
	c = p + pp
	if c > n:
		print(i)
		exit()
	i += 1
	pp = p
	p = c


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()


from __future__ import division, print_function
from sys import stdin, stdout
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd
from fractions import Fraction

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n // i
	if n > 2:
		s.add(n)
	return s

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)
n = ii()
count = 0
(a, b) = (2, 1)
while a <= n:
	(a, b) = (a + b, a)
	count += 1
print(count)


n = int(input())
l = [1, 2]
for i in range(100):
	l.append(l[-1] + l[-2])
for i in range(100):
	if l[i] > n:
		print(i - 1)
		break


def f():
	(a, b) = (1, 1)
	while True:
		yield a
		(a, b) = (a + b, a)

def main():
	n = int(input())
	for (i, x) in enumerate(f()):
		if x > n:
			print(i - 1)
			return
main()


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)


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))


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


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())
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)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(n,) = Neo()
t = 0
(k1, k2) = (2, 1)
while k1 <= n:
	t += 1
	(k1, k2) = (k1 + k2, k1)
print(t)


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


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


import math
n = int(input())
if 1:
	l = []
	q = []
	a = 0
	b = 1
	ans = 1
	c = a + b
	n = n - 2
	while c <= n:
		a = b
		b = c
		n = n - c
		c = a + b
		ans += 1
	print(ans)


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)


def main():
	num = int(input())
	num1 = 1
	num2 = 2
	tmp = 0
	cont = 0
	while tmp <= num:
		tmp = num1 + num2
		num1 = num2
		num2 = tmp
		cont += 1
	print(cont)
main()


n = int(input())
a = 1
b = 1
c = 1
while b <= n:
	tmp = b
	b = a + b
	a = tmp
	c += 1
if b == n:
	print(c - 1)
else:
	print(c - 2)


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())
(x, y, cnt, s) = (1, 1, 0, 0)
while s + y < n:
	s += y
	(x, y) = (x + y, x)
	cnt += 1
print(cnt)


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())
i = 0
fib1 = 1
fib2 = 1
x = 2
while x <= n:
	x = fib2 + fib1
	(fib1, fib2) = (fib2, x)
	i += 1
print(i - 1)


n = int(input())
if n == 2:
	print(1)
elif n == 3:
	print(2)
else:
	a = 2
	b = 3
	res = 2
	while True:
		res += 1
		c = a + b
		if c > n:
			break
		a = b
		b = c
	print(res - 1)


a = []
a.append(1)
a.append(1)
n = int(input())
if n == 2:
	print(1)
	exit(0)
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


def main():
	try:
		while True:
			s = int(input()) - 2
			if s == 0:
				print(1)
			else:
				a = b = 1
				result = 1
				while s >= b:
					s -= b
					result += 1
					(a, b) = (b, a + b)
				print(result)
	except EOFError:
		pass
main()


import bisect
n = int(input())
f = [0] * (10 ** 2 + 1)
f[0] = f[1] = 1
for i in range(2, 10 ** 2 + 1):
	f[i] = f[i - 1] + f[i - 2]
print(bisect.bisect_right(f, n) - 2)


n = int(input())
x = 1
y = 1
z = 2
ans = 0
while n >= z:
	x = y
	y = z
	z = x + y
	ans += 1
print(ans)


def fibo(n):
	f0 = 0
	f1 = 1
	if n == 0:
		fibo = 0
	elif n == 1:
		fibo = 1
	else:
		for i in range(1, n):
			fibo = f0 + f1
			f0 = f1
			f1 = fibo
	return fibo
n = int(input())
ans = 0
for k in range(n + 5):
	if fibo(k) > n:
		ans = k - 3
		break
	else:
		pass
print(ans)


fib = [0] * 2
fib[0] = 2
fib[1] = 3

def func(x):
	global fib
	if x == 2:
		return 1
	if x == 3:
		return 2
	while fib[-1] <= x:
		fib.append(fib[-1] + fib[-2])
	return len(fib) - 1
n = int(input())
print(func(n))


n = int(input())
prefix = [1, 1, 2]
now = 0
for i in range(85):
	prefix.append(prefix[-1] + prefix[-2])
while n >= prefix[now] + 1:
	n -= prefix[now]
	now += 1
print(now)


ans = 1
a = 1
b = 2
n = int(input())
if n == 1:
	print(0)
elif n == 2:
	print(1)
else:
	while a + b <= n:
		ans += 1
		temp = a + b
		a = b
		b = temp
	print(ans)


import math
n = int(input())
res = 1
if n > 2:
	res = 2
a = 2
b = 3
while a + b <= n:
	res += 1
	(a, b) = (b, a + b)
print(res)


n = int(input())
i1 = 1
i2 = 2
sol = 0
while i2 <= n:
	aux = i1 + i2
	i1 = i2
	i2 = aux
	sol = sol + 1
print(sol)


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)


n = int(input())
ans = 0
cl = [1, 2, 3]
if n <= 4:
	print([1, 2][n > 2])
else:
	i = 2
	while cl[i] <= n:
		cl += [cl[i] + cl[i - 1]]
		i += 1
	print(i - 1)


n = int(input())
arr = [1, 2]
while arr[-1] < 10 ** 18:
	l = arr[-1] + arr[-2]
	arr.append(l)
ans = 0
for i in range(len(arr)):
	if arr[i] <= n:
		ans = i
print(ans)


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
r = range
(n,) = gil()
(a, b) = (1, 2)
ans = 1
while b + a <= n:
	(a, b) = (b, a + b)
	ans += 1
print(ans)


n = int(input())
a = [0] * 20000
a[0] = 1
a[1] = 2
i = 1
while a[i] <= n:
	i += 1
	a[i] = a[i - 1] + a[i - 2]
print(i - 1)


from math import ceil, log, sqrt
phi = 0.5 * (sqrt(5) + 1)

def solve(n):
	(a, b) = (1, 2)
	i = 0
	while b <= n:
		i += 1
		(a, b) = (b, a + b)
	return i
print(solve(int(input())))


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


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	(n,) = aj()
	(a, b) = (2, 1)
	c = 0
	while a <= n:
		(a, b) = (a + b, a)
		c += 1
	print(c)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


import io
import os
players = int(input())
ans = 0
to_win_n_games = [1, 2]
n = 1
while True:
	if to_win_n_games[n] > players:
		break
	to_win_n_games.append(to_win_n_games[n] + to_win_n_games[n - 1])
	n += 1
print(n - 1)


n = int(input())
if n <= 2:
	print(n - 1)
	exit()
fib = [0, 1]
while fib[-1] <= n:
	fib.append(fib[-1] + fib[-2])
print(len(fib) - 4)


n = int(input())
(x, y) = (1, 1)
z = -1
for i in range(0, n + 1):
	if y > n:
		print(i - 1)
		break
	z = x + y
	x = y
	y = z


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())))


fib = [0, 1]
for i in range(2, 100):
	fib.append(fib[i - 1] + fib[i - 2])
fib = fib[2:]
n = int(input())
maks = 0
for i in range(len(fib)):
	if n >= fib[i]:
		maks = max(maks, i)
	else:
		break
print(maks)


n = int(input())
dp = [0 for i in range(100)]
dp[0] = 1
dp[1] = 2
i = 1
while 1:
	if dp[i] == 0:
		dp[i] = dp[i - 1] + dp[i - 2]
	if dp[i] > n:
		print(i - 1)
		break
	else:
		i += 1


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


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
series = [2, 3]
x = 5
while x < 10 ** 18:
	series.append(x)
	x += series[-2]
n = Int()
ans = bisect_right(series, n)
print(ans)


from sys import stdout
n = int(input())
dp = [0 for i in range(100)]
dp[0] = 1
dp[1] = 2
for i in range(2, n + 10):
	if dp[i - 1] > n:
		stdout.write(str(i - 2))
		break
	dp[i] = dp[i - 1] + dp[i - 2]


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)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 998244353

def solve():
	N = getInt()
	fibs = [1, 2]
	while fibs[-1] <= 10 ** 18:
		fibs.append(fibs[-1] + fibs[-2])
	i = 0
	while fibs[i] <= N:
		i += 1
	return i - 1
print(solve())


def rints():
	return list(map(int, input().split()))

def ri():
	return int(input())
n = ri()
i = 1
prev = 1
cur = 2
while cur + prev <= n:
	(cur, prev) = (cur + prev, cur)
	i += 1
print(i)


def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())
n = ii()
ans = 0
(p, q) = (2, 1)
while p <= n:
	(p, q) = (p + q, p)
	ans += 1
print(ans)


player = int(input())

def thefunc(players):
	if players == 1 or players == 2:
		return 1
	if players == 3:
		return 2
	min_players_on_before_level = 2
	min_players_on_this_level = 3
	rounds = 1
	while min_players_on_this_level <= player:
		temp = min_players_on_before_level
		min_players_on_before_level = min_players_on_this_level
		min_players_on_this_level = temp + min_players_on_this_level
		rounds += 1
	return rounds
print(thefunc(player))


n = int(input())
a = 1
b = 1
c = 0
while a + b <= n:
	t = a
	a = a + b
	b = t
	c += 1
print(c)


f = [0, 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]
n = int(input())
for i in range(len(f)):
	if f[i] > n:
		break
print(i - 1)


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))