//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int dig(int x)
{
  int res = 0;
  while (x > 0)
  {
    ++res;
    x /= 10;
  }
  return res;
}

int jum(LL x)
{
  int res = 0;
  while (x > 0)
  {
    res += x % 10;
    x /= 10;
  }
  return res;
}

/// begin

typedef complex<double> base;

void fft (vector<base> & a, bool invert) {
  int n = (int) a.size();
  if (n == 1)  return;
 
  vector<base> a0 (n/2),  a1 (n/2);
  for (int i=0, j=0; i<n; i+=2, ++j) {
    a0[j] = a[i];
    a1[j] = a[i+1];
  }
  fft (a0, invert);
  fft (a1, invert);
 
  double ang = 2*PI/n * (invert ? -1 : 1);
  base w (1),  wn (cos(ang), sin(ang));
  for (int i=0; i<n/2; ++i) {
    a[i] = a0[i] + w * a1[i];
    a[i+n/2] = a0[i] - w * a1[i];
    if (invert)
      a[i] /= 2,  a[i+n/2] /= 2;
    w *= wn;
  }
}

void multiply (const vector<LL> & a, const vector<LL> & b, vector<LL> & res) {
  vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
  size_t n = 1;
  while (n < max (a.size(), b.size()))  n <<= 1;
  n <<= 1;
  fa.resize (n),  fb.resize (n);
 
  fft (fa, false),  fft (fb, false);
  for (size_t i=0; i<n; ++i)
    fa[i] *= fb[i];
  fft (fa, true);
 
  res.resize (n);
  for (size_t i=0; i<n; ++i)
    res[i] = LL (fa[i].real() + 0.5);
}

// fft

int k;
bool dah[100005];
bool dua[100005];
vi mods;

int solve(int k)
{
  RESET(dah,0); RESET(dua, 0); mods.clear();
  int now = 1 % k;
  while (!dah[now])
  {
    dah[now] = 1;
    mods.pb(now);
    now = (now * 10) % k;
  }
  // debug("%d\n",SIZE(mods));
  if (dah[0]) return 1;
  REP(i,SIZE(mods)) if (dah[k - mods[i]]) return 2;
  
  vector<LL> a(k);
  vector<LL> b(k);
  REP(i,SIZE(mods)) a[mods[i]] = b[mods[i]] = 1;
  vector<LL> c;
  multiply(a,b,c);
  REP(i,SIZE(c)) if (c[i] > 0) dua[i%k] = 1;

  REP(i,SIZE(mods)) if(dua[k - mods[i]]) return 3;
  FOR(i,1,k) if(dua[i] && dua[k - i]) return 4;


  RESET(dah,0);
  queue<pii> q;
  REP(i,SIZE(mods))
  {
    dah[mods[i]] = 1;
    q.push(mp(mods[i],1));
  }
  while (!q.empty())
  {
    int now = q.front().fi;
    int steps = q.front().se;
    q.pop();
    if (now == 0)
    {
      return steps;
    }
    REP(i,SIZE(mods))
    {
      int nxt = now + mods[i];
      if (nxt >= k) nxt -= k;
      if (!dah[nxt])
      {
        dah[nxt] = 1;
        q.push(mp(nxt,steps+1));
      }
    }
  }
  return -1;
}

int bf(int k,int lim=1000000)
{
  int res = INF;
  FORN(i,1,lim)
  {
    LL temp = (LL)k * i;
    MIN(res,jum(temp));
  }
  return res;
}

int main()
{
  // int res = 0;
  // // FORN(i,2,10000) MAX(res,solve(i));
  // VALUE(solve(79992));
  // VALUE(res);return 0;
  scanf("%d",&k);
  printf("%d\n",solve(k));
  // VALUE(solve(90001));
  // FORN(i,90000,100000)
  // {
  //   debug("%d %d\n",i,solve(i));
  // }
  // debug("%d\n",bf(k));
  // FORN(i,1,1000)
  // {
  //   if (solve(i) > bf(i,10000000))
  //   { 
  //     debug("%d %d %d\n",i,solve(i),bf(i,10000000));
  //     assert(false);
  //   }
  // }
  return 0;
}










Measured memory_bytes: 20000