//

 //by coolxxx

 //

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<iomanip>

 #include<memory.h>

 #include<time.h>

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<stdbool.h>

 #include<math.h>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define abs(a) ((a)>0?(a):(-(a)))

 #define sqr(a) (a)*(a)

 #define swap(a,b) (a)^=(b),(b)^=(a),(a)^=(b)

 #define eps 1e-8

 #define S 10000

 #define MAX 0x7f7f7f7f

 #define PI 3.1415926535897

 #define N 14

 #define M 100000

 using namespace std;

 int n,m,cas,lll,ans;

 int r[N]={,,,,,,,,};

 int d[]={-,-,,};

 int q[M][N]={,,,,,,,,};

 int v[M];

 bool u[];

 bool ok(int x,int y)

 {

     if(y==-)return (x/>);

     if(y==-)return (x%>);

     if(y==) return (x%<);

     if(y==) return (x/<);

 }

 int spfa()

 {

     int i,j,now,h=-,t=;

     int x;

     u[m%r[]]=;

     while(h++<t)

     {

         for(x=,i=;i<;i++)

         {

             x+=q[h][i]*r[-i];

             if(q[h][i]==)now=i;

         }

         if(x==n)return v[h];

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

         {

             if(ok(now,d[i]))

             {

                 memcpy(q[t+],q[h],sizeof(q[h]));

                 swap(q[t+][now],q[t+][now+d[i]]);

                 for(x=,j=;j<;j++)

                     x+=q[t+][j]*r[-j];

                 if(!u[x])

                 {

                     v[++t]=v[h]+;

                     u[x]=;

                 }

             }

         }

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     //freopen("1.txt","r",stdin);

     //freopen("2.txt","w",stdout);

     #endif

     int i,j,k;

     //while(~scanf("%s%s",sn,sm))

     while(~scanf("%d",&n) && n)

     {

         m=;

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

     }

     return ;

 }

 /*

 //

 //

 */