#include <bits/stdc++.h>
#define INT long long int
using namespace std;
deque<INT> q;
INT n, d[100010], N, ans;
int main() {
  freopen(".10.in","w",stdout);
  cin>>n;
  cout<<n;
  memset(d, 0x3f, sizeof(d));
  freopen(".10.out","w",stdout);
  d[1]=1, q.push_back(1);
  while( !q.empty() )
  {
      INT now = q.front(); q.pop_front();
      if( d[(now+1)%n] > d[now]+1 ) q.push_back((now+1)%n), d[(now+1)%n] = d[now]+1;
      if( d[(now*10)%n] > d[now] ) q.push_front((now*10)%n), d[(now*10)%n] = d[now];
  }
  cout<<d[0]<<endl;
}