// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



const int mx = 1e5+5;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

typedef pair<int,int>pii;

typedef pair<int,pii>piii;



#define  sf scanf

#define  pf printf



#define  input freopen("input.txt","r",stdin)

#define  output freopen("output.txt","w",stdout)



#define  inf 1e8

#define  ff first

#define  ss second

#define  MP make_pair

#define  pb push_back

#define  all(v) v.begin(), v.end()

#define  printcase(cases) printf("Case %d:", cases);

#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())

#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)

#define  endl printf("\n")

#define  __lcm(a, b) ((a*b)/__gcd(a, b))



int  Set(int N,int pos){return N=N | (1<<pos);}

int  reset(int N,int pos){return N= N & ~(1<<pos);}

bool check(int N,int pos){return (bool)(N & (1<<pos));}

vector<pii>adj[mx];

int dis[mx];

int k;



int bfs(int src)

{

    priority_queue<pii, vector<pii>, greater<pii> >pq;

    pq.push(make_pair(0, src));

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

    dis[src] = 0;

    while(!pq.empty())

    {

        pii top = pq.top();

        pq.pop();

        int u = top.ss;

        int curw = top.ff;

        for(int i = 0; i < adj[u].size(); i++)

        {

            int v = adj[u][i].ff;

            int w = adj[u][i].ss;

            if(w+curw<dis[v])

            {

                dis[v] = curw+w;

                pq.push(make_pair(dis[v], v));

            }

        }

    }

    //for(int i = 0; i < k; i++) cout << dis[i] << ' ';

    //cout << '\n';

    return dis[k];

}

int main()

{

    sf("%d", &k);



    for(int x = 0; x <= k; x++)

    {

        for(int p = 0; p <= 9; p++)

        {

            int u = x;

            int v = ((10*x)+p)%k;

            if(v == 0) v = k;

            if(v==k && u==0 && p==0) continue;

            adj[u].push_back(make_pair(v, p));

        }

    }

    int ans = bfs(0);

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

    return 0;

}


// Optimized solution to the same problem (faster):


#include <bits/stdc++.h>



using namespace std;



#define fread(x)        freopen(x,"r",stdin)

#define fwrite(x)       freopen (x,"w",stdout)



#define min3(a,b,c)     min(a,min(b,c))

#define max3(a,b,c)     max(a,max(b,c))

#define min4(a,b,c,d)   min(a,min(b,min(c,d)))

#define max4(a,b,c,d)   max(a,max(b,max(c,d)))

#define MEMSET(a,x)     memset(a,x,sizeof(a))

#define ABS(x)          ((x)<0?-(x):(x))

#define keepunique(v)   (v).erase(unique(all(v)),v.end())



#define white           1

#define grey            2

#define black           3



#define ll              long long

#define pb              push_back

#define pf              push_front

#define INF             9e18

#define PI              acos(-1.0)

#define pii             pair<int,int>

#define pll             pair<ll, ll>



#define all(v)          v.begin(), v.end()



#define fastread        ios_base::sync_with_stdio(0);cin.tie(nullptr);

int on(int N,int pos){return N=N | (1<<pos);}

int off(int N,int pos){return N= N & ~(1<<pos);}

bool check(int N,int pos){return (bool)(N & (1<<pos));}

int lcm(int a, int b){return (a*b)/__gcd(a, b);}

//======================= let the game begin ====================//

const int maxn = 1e5 + 5;

int dis[maxn];

#define inf 1000005



int main(){

  fastread

  int k;

  cin>>k;

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

    dis[i]=inf;

  }

  dis[1]=1;

  deque<int>que;

  que.push_back(1);

  while(!que.empty()){

    int s = que.front();

    que.pop_front();

    if(dis[(s+1)%k] > dis[s]+1){

      dis[(s+1)%k]=dis[s]+1;

      que.pb((s+1)%k);

    }

    if(dis[(s*10)%k] > dis[s]){

      dis[(s*10)%k]=dis[s];

      que.pf((s*10)%k);

    }

  }

  cout<<dis[0]<<endl;

}


// Fastest known solution for this problem: