#include<bits/stdc++.h>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

const int N=3e5+;

const int p=1e9+;

int k,cnt;

int dis[N],last[N];

bool vis[N];

struct orz{

    int v,nex,s;}e[N*];

queue<int>q;

void add(int x,int y,int z)

{

    cnt++;

    e[cnt].v=y;

    e[cnt].nex=last[x];

    last[x]=cnt;

    e[cnt].s=z;

}

void spfa()

{

    for (int i=;i<k;i++) dis[i]=inf;

    dis[]=; vis[]=;

    q.push();

    while (!q.empty())

    {

        int now=q.front(); q.pop();

        for (int i=last[now];i;i=e[i].nex)

        {

            if (dis[e[i].v]>dis[now]+e[i].s)

            {

                dis[e[i].v]=dis[now]+e[i].s;

                if (!vis[e[i].v])

                {

                    vis[e[i].v]=;

                    q.push(e[i].v);

                }

            }

        }

        vis[now]=;

    }

}

int main()

{

    scanf("%d",&k);

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

    {

        add(i,(i+)%k,);

        add(i,i*%k,);

    }

    spfa();

    printf("%d\n",dis[]+);

    return ;

}