#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <limits>
#include <algorithm>
#include <queue>
#include <vector>
#include <numeric>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <tuple>
#include <cassert>

#ifndef IO_H
#define IO_H

#include <cstdio>
#include <limits>

namespace {

class TokenizeReader {
public:
  TokenizeReader() = delete;
  TokenizeReader(FILE* file, int buffer_len);
  ~TokenizeReader();
  void Read(char* s, size_t& len, int max_len = std::numeric_limits<int>::max());
  bool HasNext();
  int NextInt();
private:
  bool EnsureRead();
  bool IsInValidCharacter(int c);

  FILE* file_;
  char* buffer_;
  int buffer_len_, pos_, read_n_;
  bool end_ = false;
};

TokenizeReader::TokenizeReader(FILE* file, int buffer_len)
  : file_(file), buffer_len_(buffer_len), pos_(0), read_n_(0) {
  buffer_ = new char[buffer_len_];
}

TokenizeReader::~TokenizeReader() {
  delete buffer_;
}

void TokenizeReader::Read(char *s, size_t &len, int max_len) {
  len = 0;
  while (EnsureRead() && IsInValidCharacter(buffer_[pos_])) pos_++;
  while ((int) len < max_len && EnsureRead()
      && !IsInValidCharacter(buffer_[pos_])) {
    s[len++] = buffer_[pos_++];
  }
}

bool TokenizeReader::HasNext() {
  static size_t unused;
  Read(nullptr, unused, 0);
  return EnsureRead();
}

int TokenizeReader::NextInt() {
  static char buf[21];
  size_t len;
  int value;
  Read(buf, len, 20);
  if (len == 0) throw -1;
  buf[len] = 0;
  sscanf(buf, "%d", &value);
  return value;
}

bool TokenizeReader::EnsureRead() {
  if (pos_ < read_n_) {
    return true;
  } else if (end_) {
    return false;
  }
  read_n_ = ::fread(buffer_, 1 /* size */, buffer_len_, file_);
  pos_ = 0;
  end_ = read_n_ == 0;
  return !end_;
}

bool TokenizeReader::IsInValidCharacter(int c) {
  return c == ' ' || c == '\t' || c == '\n' || c == EOF;
}

}

#endif  // IO_H

namespace {

#define for_each_test_cases(T, BUFFSIZE)            \
  TokenizeReader reader(::stdin, BUFFSIZE);         \
  int T;                                            \
  scanf("%d", &T);                                  \
  for (int cas = 1; cas <= T; cas++)

}  // namesapce

#define MaxN 100005
#define MaxE 100005 * 2
#ifndef SPFA_H
#define SPFA_H

#ifndef GRAPH_H
#define GRAPH_H

#define MACRO_GRAPH_EXTRA_FIELDS int weight;

#ifndef SIMPLE_GRAPH_H
#define SIMPLE_GRAPH_H

#include <cassert>

#ifndef MaxE
#define MaxE 10005
#endif

#ifndef MACRO_GRAPH_EXTRA_FIELDS
#define MACRO_GRAPH_EXTRA_FIELDS
#endif // MACRO_GRAPH_EXTRA_FIELDS

struct edge_t {
  int to;
  MACRO_GRAPH_EXTRA_FIELDS
  edge_t* next;

  struct iterator {
    edge_t* iter;
    iterator(edge_t* _iter) : iter(_iter) {}
    iterator& operator++(int) {
      assert(iter);
      iter = iter->next;
      return *this;
    }
    bool has_next() const { return iter != NULL; }
    edge_t& operator*() const { return *iter; }
    edge_t* operator->() const { return iter; }
  };
  
} edges[MaxE], *cure;

inline edge_t* add_edge(edge_t** head, int u, int v) {
  cure->to = v;
  cure->next = head[u];
  head[u] = cure;
  return cure++;
}

#define foreach(head, it) for (edge_t::iterator it = head; it.has_next(); it++)

#endif // SIMPLE_GRAPH_H

inline void add_edge(edge_t** head, int u, int v, int weight) {
  cure->to = v;
  cure->weight = weight;
  cure->next = head[u];
  head[u] = cure++;
}

#endif

#ifndef MaxN
#define MaxN 10005
#endif

void spfa(int s, int n, edge_t **head, long long *distance) {
  static int queue[MaxN];
  static bool visited[MaxN];
  int f = 0, b = 0, u, v;
  for (int i = 0; i <= n; i++) {
    distance[i] = 0x3F3F3F3F3F3F3F3FLL;
    visited[i] = false;
  }
  distance[s] = 0;
  queue[b++] = s;
  while (f != b) {
    u = queue[f++];
    if (f == MaxN) f = 0;
    visited[u] = false;
    for (edge_t *iter = head[u]; iter; iter = iter->next) {
      v = iter->to;
      if (distance[v] - distance[u] > iter->weight) {
        distance[v] = distance[u] + iter->weight;
        if (!visited[v]) {
          queue[b++] = v;
          if (b == MaxN) b = 0;
          visited[v] = true;
        }
      }
    }
  }
}

#endif
edge_t* head[MaxN];
long long distance[MaxN];

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    cure = edges;
    for (int i = 0; i < n; i++) head[i] = nullptr;
    for (int i = 0; i < n; i++) {
      add_edge(head, i, (i + 1) % n, 1);
      add_edge(head, i, (i * 10) % n, 0);
    }
    spfa(1, n, head, distance);
    printf("%lld\n", distance[0] + 1);
  }
  return 0;
}



Measured memory_bytes: 5376