#include #include using namespace std; int p,depth=0;

int gcd( int a,int b ) { if ( !b ) return a; return gcd( b,a%b ); }

bool IDAstar( int sum,int x,int y ) { if ( sumdepth ) { if ( xp ) return 1; else return 0; } if ( x<<(depth-sum)<p ) return 0; if ( p%(gcd(x,y))!=0 ) return 0;

int a,b;

a=x+y; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+y; b=x;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+x; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+x; b=x;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=y+y; b=x; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=y+y; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x-y; b=x; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x-y; b=y; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;

return 0;

}

int main() { scanf( "%d",&p );

while ( !IDAstar( 0,1,0 ) ) depth++;

printf( "%d",depth );

}