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 ≤ 1018) — 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.
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class TestClass {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	
	public static class Queue{
		private class node{
			int val;
			node next;
			node(int a){
				val = a;
				next = null;
			}
		}
		node head,tail;
		Queue(){
			head = null;
			tail = null;
		}
		public void EnQueue(int a){
			if(head==null){
				node p = new node(a);
				head = p;
				tail = p;
			}
			else{
				node p = new node(a);
				tail.next = p;
				tail = p;
			}
		}
		public int DeQueue(){
			int a = head.val;
			head = head.next;
			return a;
		}
		public boolean isEmpty(){
			return head==null;
		}
	}
	public static long pow(long x,long y,long m){
		if(y==0)
    		return 1;
    	long k = pow(x,y/2,m);
    	if(y%2==0)
    		return (k*k)%m;
    	else
    		return (((k*k)%m)*x)%m;
    }
	static long Inversex = 0,Inversey = 0;
	public static void InverseModulo(long a,long m){
		if(m==0){
			Inversex = 1;
			Inversey = 0;
		}
		else{
    		InverseModulo(m,a%m);
    		long temp = Inversex;
    		Inversex = Inversey;
    		Inversey = temp+ - (a/m)*Inversey;
    	}
    }
    static long mod1 = 1000000007;
    static long mod2 = 1000000009;
	public static long gcd(long a,long b){
		if(a%b==0)
			return b;
		return gcd(b,a%b);
	}
	public static boolean isPrime(long a){
		if(a==1)
			return false;
		else if(a==2||a==3)
			return true;
		for(long i=2;i<=Math.sqrt(a);i++)
			if(a%i==0)
				return false;
		return true;
	}
	public static double distance(int a,int b,int x,int y){
		return Math.sqrt(((long)(a-x)*(long)(a-x))+((long)(b-y)*(long)(b-y)));
	}
	public static class Pair implements Comparable<Pair> {
		long u;
		long v;
		BigInteger bi;
		public Pair(long u, long v) {
			this.u = u;
			this.v = v;
		}
		public int hashCode() {
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31 * hu + hv;
		}
		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return u == other.u && v == other.v;
		}
		public int compareTo(Pair other) {
			return Long.compare(u, other.u) != 0 ? Long.compare(u, other.u) : Long.compare(v, other.v);
		}
		public String toString() {
			return "[u=" + u + ", v=" + v + "]";
		}
	}
	public static int seive(int a[],boolean b[],ArrayList c){
		int count = 0;
		for(int i=2;i*i<a.length;i++){
			if(!b[i]){
				for(int j=i*i;j<a.length;j=j+i)
					b[j] = true;
				c.add(i);
				a[count++] = i;
			}
		}
		return count;
	}
	public static void MatrixMultiplication(int a[][],int b[][],int c[][]){
		for(int i=0;i<a.length;i++){
			for(int j=0;j<b[0].length;j++){
				c[i][j] = 0;
				for(int k=0;k<b.length;k++)
					c[i][j]=(int)((c[i][j]+((a[i][k]*(long)b[k][j])%mod1))%mod1);
			}
		}
	}
	public static void Equal(int arr[][],int temp[][]){
		for(int i=0;i<arr.length;i++){
			for(int j=0;j<arr.length;j++)
				temp[i][j] = arr[i][j];
		}
	}
	static long max1 = (long) ((long) -1*10e15),index = -1,temp = -1;
	public static long dfs(ArrayList<Integer> a[],boolean u[],int arr[],int p,boolean v){
		if(p==temp)
			return (long) (-1*10e17);
		if(!v){
			u[p] = true;
			long count = (long) (-1*10e15);
			if((p!=0&&a[p].size()>2)||(p==0&&a[p].size()>1)){
				for(int i=0;i<a[p].size();i++)
					if(!u[a[p].get(i)])
						count = Math.max(count,dfs(a,u,arr,a[p].get(i),true));
			}
			else{
				for(int i=0;i<a[p].size();i++)
					if(!u[a[p].get(i)])
						count = Math.max(count,dfs(a,u,arr,a[p].get(i),false));
			}
			return count;
		}
		else{
			u[p] = true;
			long count = arr[p];
			for(int i=0;i<a[p].size();i++){
				if(!u[a[p].get(i)]){
					long ui = dfs(a,u,arr,a[p].get(i),true);
					count+=ui;
				}
			}
			if(max1<count){
				max1 = count;
				index = p;
			}
			return count;
		}
	}
	private static void soln(){
		long n = nL();
		if(n==2){
			pw.println("1");
			return ;
		}
		else if(n==3){
			pw.println("2");
			return ;
		}
		long count = 0,x = 1,y = 2;
		while(x+y<=n){
			long temp = x+y;
			x = y;
			y = temp;
			count++;
		}
		pw.println(count+1);
	}
	public static void main(String[] args) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		soln();
		pw.close();
	}
	// To Get Input
	// Some Buffer Methods
	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}
	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}
	private static int nI() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private static long nL() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	private static String nLi() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}
	private static int[] nIA(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nI();
		return arr;
	}
	private static long[] nLA(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nL();
		return arr;
	}
	private static void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++)
			pw.print(arr[i] + " ");
		pw.println();
		return;
	}
	private static void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++)
			pw.print(arr[i] + " ");
		pw.println();
		return;
	}
	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}