#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int head[1000000];
int nx[1000000];
int a[10000000];
int b[1000000];
int s[1000000];
int cnt=0;
struct queue
{
    int a,b,s;
}q[1000000];
int size;
int p;
const int mod=999997;
int gcd(int a,int b)
{
   while(b)
   {
      int t=a%b;
      a=b;
      b=t;
   }
   return a;
}
void swap(int a,int b)
{
   queue x=q[a];
   q[a]=q[b];
   q[b]=x;
}
int hash(int aa,int bb)
{
    int x=(aa*p+bb)%mod;
    if(x<0) return (aa+bb)%mod;
    return x;
}
int find(int aa,int bb)
{
   for(int t=head[hash(aa,bb)];t!=-1;t=nx[t])
      if(a[t]==aa&&b[t]==bb) return t;
   return -1;
}
int h(int x)
{
   int big=max(q[x].a,q[x].b);
   if(big==0) return 10000;
   for(int i=0;;i++)
      if((big<<i)>=p) return q[x].s+i;
}
bool ins(int aa,int bb,int ss)
{
   int code;
   if(aa<bb){code=aa;aa=bb;bb=code;}
   //if(aa==10&&bb==3) printf("[%d %d] ",size,cnt);
   if((code=find(aa,bb))>=0)
     if(ss>=s[code])
      return false;
   if(aa==0&&bb==0) return false;
   if(p%gcd(aa,bb)) return false;
   code=hash(aa,bb);
   cnt++;
   a[cnt]=aa;
   b[cnt]=bb;
   s[cnt]=ss;
   nx[cnt]=head[code];
   head[code]=cnt;
   ////////
   size++;
   q[size].a=aa;
   q[size].b=bb;
   q[size].s=ss;
   int now=size;
   while((now>=2)&&(h(now)<h(now/2)))swap(now,now/2),now/=2;
   if(q[1].a==p||q[1].b==p)
   {
      printf("%d",q[1].s);
      return true;
   }
   return false;
}
void del()
{
   swap(1,size);
   size--;
   int now,st;
   for(now=1;(st=now*2)<=size;now=st)
   {
      if(st+1<=size&&h(st+1)<h(st))st++;
      if(h(now)<=h(st)) break;
      swap(now,st);
   }
}
int main()
{
   int i,j,k;
   scanf("%d",&p);
   memset(head,-1,sizeof(head));
   for(size=0,ins(1,0,0);size;del())
      if(ins(q[1].a+q[1].b,q[1].b,q[1].s+1)||
      ins(q[1].a+q[1].b,q[1].a,q[1].s+1)||
      ins(q[1].a-q[1].b,q[1].b,q[1].s+1)||
      ins(q[1].a-q[1].b,q[1].a,q[1].s+1)||
      ins(q[1].a+q[1].a,q[1].a,q[1].s+1)||
      ins(q[1].a+q[1].a,q[1].b,q[1].s+1)||
      ins(q[1].b+q[1].b,q[1].a,q[1].s+1)||
      ins(q[1].b+q[1].b,q[1].b,q[1].s+1)) break;
   getchar();
   getchar();
   return 0;
}