#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
#define db(x) cout << #x << " = " << (x) << endl
#define fend(x) ((x) & ((x) + 1)) - 1
#define fenu(x) (x) | ((x) + 1)
#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define forr(i, b, e) for (int i = b; i < (int)e; ++i)
#define ft first
#define len(s) s.length()
#define mp make_pair
#define pob pop_back
#define pof pop_front
#define pub push_back
#define puf push_front
#define sc second

typedef double dbl;
typedef long double ldbl;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

template <typename T>
using vec = std::vector<T>;

const long long MILLER_RABIN = 3215031751;
const long double PI = acos(-1);

#if __cplusplus >= 201103L

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct ConfigIO {
  ConfigIO() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
  }
} cnf_io;

// struct config_rand {
//    config_rand() {
//        srand(chrono::duration_cast<chrono::nanoseconds>(
//                chrono::high_resolution_clock::now().time_since_epoch()).count());
//    }
//} cnf_rand;

namespace std {
template <>
struct hash<pair<int, int>> {
  size_t operator()(const pair<int, int>& x) const {
    return (x.first * 71ull + x.second) % ((int)1e9 + 7);
  }
};

template <>
struct hash<vector<int>> {
  size_t operator()(const vector<int>& v) const {
    size_t hsh = 0;
    for (int i = 0; i < v.size(); ++i) {
      hsh = (hsh * 71ull + v[i]) % (int)(1e9 + 7);
    }
    return hsh;
  }
};
}  // namespace std

// __builtin_popcount(x) - Returns the number of 1-bits in x.
// __builtin_parity(x) - Returns the parity of x, i.e. the number of 1-bits in x
// modulo 2.
// __builtin_ffs(x) - Returns one plus the index of the least significant 1-bit
// of x, or if x is zero, returns zero.
// __builtin_clz(x) - Returns the number of leading 0-bits in x, starting at the
// most significant bit position. If x is 0, the result is undefined.
// __builtin_ctz(x) - Returns the number of trailing 0-bits in x, starting at
// the least significant bit position. If x is 0, the result is undefined.

// inline string tobin(long long x) { bitset<63>(x).to_string(); }

template <class T>
void Trace(T collection) {
  for (auto elem : collection) {
    cout << elem << " ";
  }
  cout << endl;
}

int GetRand() {
  static mt19937_64 gen;
  static uniform_int_distribution<int> dis;
  return dis(gen);
}

#endif

struct Pair {
#define __TYPE__ int
  __TYPE__ x, y;

  Pair() {
  }

  Pair(__TYPE__ _x, __TYPE__ _y) : x(_x), y(_y) {
  }

  friend __TYPE__ Cross(const Pair& p1, const Pair& p2) {
    return p1.x * p2.y - p1.y * p2.x;
  }

  friend __TYPE__ Dot(const Pair& p1, const Pair& p2) {
    return p1.x * p2.x + p1.y * p2.y;
  }

  friend bool operator<(const Pair& p1, const Pair& p2) {
    return p1.x > p2.x || (p1.x == p2.x && p1.y < p2.y);
  }

  friend bool operator==(const Pair& p1, const Pair& p2) {
    return p1.x == p2.x && p1.y == p2.y;
  }

  struct Hasher {
    size_t operator()(const Pair& p) const {
      return p.x * 1234567ULL + p.y;
    }
  };
};

template <typename T>
inline T& RD(T& x) {
  char c;
  while (!isdigit(c = getchar()))
    ;
  x = c - '0';
  while (isdigit(c = getchar()))
    x = x * 10 + c - '0';
  return x;
}

template <typename _Type>
void print(_Type arg) {
  cout << arg << endl;
}

template <typename _Type, typename... _Args>
void print(_Type first_arg, _Args&&... args) {
  cout << first_arg << " ";
  print(std::forward<_Args>(args)...);
}

template <typename _Type>
void scan(_Type& arg) {
  cin >> arg;
}

template <typename _Type>
void scan(vector<_Type>& v) {
  for (size_t i = 0; i < v.size(); ++i) {
    scan(v[i]);
  }
}

template <typename _Type, typename... _Args>
void scan(_Type& first_arg, _Args&&... args) {
  scan(first_arg);
  scan(std::forward<_Args>(args)...);
}

class Solution {
  const int MS = 50;
  const int ML = 1e5 + 10;
  vec<vec<char>> used;

 public:
  void Solve() {
    int K;
    scan(K);
    used.assign(MS, vec<char>(K, 0));
    queue<pair<int, int>> q;
    forr(i, 1, 10) {
      q.push({i, i % K});
      used[i][i % K] = 1;
    }
    while (!q.empty()) {
      auto cur = q.front();
      q.pop();
      forn(i, 10) {
        auto nxt = mp(cur.ft + i, (10 * cur.sc + i) % K);
        if (nxt.ft < MS && !used[nxt.ft][nxt.sc]) {
          q.push(nxt);
          used[nxt.ft][nxt.sc] = 1;
        }
      }
    }
    forn(i, MS) {
      if (used[i][0]) {
        cout << i << endl;
        return;
      }
    }
  }
};

int main() {
#ifdef HOME
  freopen("home.in", "r", stdin);
  freopen("home.out", "w", stdout);
#endif

  int tests = 1;
  // scan(tests);
  for (int test = 1; test <= tests; ++test) {
    Solution().Solve();
    // cin.clear();
    // cin.seekg(0, ios::beg);
  }
  return 0;

#ifdef HOME
  cout << "\n\nTime: " << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
}

Measured memory_bytes: 21176