C++ :

#include <cstdio>
#include <iostream>
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 ( sum==depth )
    {
        if ( x==p ) 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 );
}