#include<stdio.h>

//we have defined the necessary header files here for this problem.

//If additional header files are needed in your program, please import here.

/* *

函数int deal(int n,int m)：处理达到(n,m)转化为(1,1)时需要的次数

首先保证n<=m

当n==1时，deal(1,m)应该返回 m-1 （规律）

当n不为1且n==m时、或当n < 1时，无法转化到(1,1) 返回无效值-1

将deal(n,m)转化为deal(n,m%n)，这里在n远远小于m时，远远比用减号要快，也不会Stackoverflow

如果deal(n,m%n)返回有效值，就把m/n这个转化次数加上返回

函数 resolve(n):对n进行从(1,n-1)(2,n-2)…(n/2,n-n/2)进行遍历调用

如果返回了合法值，就和min比较替换

返回时注意要加上首次拆开时的1次

*/

int deal(int n,int m);

int resolve(int n);

int main(){

  int n;

  while(scanf("%d",&n)!=EOF){

      if(n==){

          printf("%d\n",);

      }else{

          printf("%d\n",resolve(n));

      }

  }

  return ;

}

int deal(int n,int m){

    int t = ;

    if(n>m){

        t=m;

        m=n;

        n=t;

    }

    if(n==){

        return m-;

    }

    if((n==m && n!=) || n<){

        return -;

    }

    int changeTimes = m/n;

    int d = deal(n,m%n);

    if(d!=-){

        return changeTimes+d;

    }

    return -;

}

int resolve(int n){

    int min = ;

    if(n<=){

        return ;

    }

    for (int i = ; i <= n/; i++)

    {

        int temp = -;

        temp = deal(i,n-i);

        if( (temp>=) && (temp<min) ){

            min = temp;

        }

    }

    return min+;

}