// 同余最短路 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N=100010,M=N*10;
int idx,h[N],to[M],ww[M],ne[M];
void add(int u,int v,int w){
  to[++idx]=v;ww[idx]=w;ne[idx]=h[u];h[u]=idx;
}
int k,d[N];

void dijkstra(int s){
  memset(d,0x3f,sizeof(d)); d[s]=0;
  priority_queue<pii,vector<pii>,greater<pii> >q;
  q.push({0,s});
  while(!q.empty()){
    auto [dd,u]=q.top();q.pop();
    if(dd!=d[u]) continue;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
signed main(){
  scanf("%lld",&k);
  for(int i=0;i<k;++i)for(int j=0;j<10;++j)add(i,(i*10+j)%k,j);
  add(k,(k*10+1)%k,1); //起点k
  
  dijkstra(k);
  cout<<d[0];
}