/*

一开始想到了简单的深搜 维护当前可用的mi数组

然后回溯用哪个 不断更新新产生的mi

这样的问题是 由于mi不断产生 搜索规模扩大

不好 不好  下面是奇丑的WA掉的代码 做个反面教材

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,ans=0x3f3f3f3f,f[],s[],top,vis[];

void Dfs(int p,int c)

{

    if(p<=||p>n*)return;

    if(f[p]==)s[++top]=p,f[p]=;

    if(p==n){ans=min(ans,c);return;}

    if(c>ans)return;

    for(int i=;i<=top;i++)

      if(vis[i]==)

        {

          vis[i]=;

          Dfs(p+s[i],c+);

          Dfs(p-s[i],c+);

          vis[i]=;

        }

}

int main()

{

    scanf("%d",&n);

    ans=n;

    Dfs(,);

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

    return ;

}

/*

正解是迭代加深

对于每次的搜索 我们限制最多能做几次运算

这样搜索的规模就大大减小

同样的维护已经得到的mi数组

数组的大小对应做了几次运算

加上几个剪枝：

如果mi中最大的<<(limit-k)都到不了n 搜索失败

生成新的mi的时候 尽量组合数大的 这样也可以减小规模

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 20

using namespace std;

int n,a[N*];

bool Dfs(int k,int limit)

{

    if(a[k]==n)return ;

    if(k==limit)return ;

    int maxx=;

    for(int i=;i<=k;i++)maxx=max(maxx,a[k]);

    if(maxx<<(limit-k)<n)return ;

    for(int i=k;i>=;i--)

      {

          a[k+]=a[i]+a[k];

          if(Dfs(k+,limit))return ;

          a[k+]=a[k]-a[i];

          if(Dfs(k+,limit))return ;

      }

    return ;

}

int find()

{

    if(n==)return ;

    a[]=;

    for(int i=;i<=N;i++)

      if(Dfs(,i))return i;

}

int main()

{

    scanf("%d",&n);

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

    return ;

}