// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

typedef pair<int, double> Pid;

typedef pair<double, int> Pdi;

typedef pair<ll, int> Pl;

typedef pair<ll, ll> Pll;

typedef pair<int, pair<int, int>> PP;

typedef pair<P, int> PPi;

constexpr double PI = 3.1415926535897932;   // acos(-1)

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

#define chadd(x, y) x = (x + y) % mod



vector<P> graph[100005];

vector<int> dist(100005, INF);



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int k;

    cin >> k;

    for(int i = 0; i < k - 1; ++i)  graph[i].push_back(P(i + 1, 1));

    graph[k - 1].push_back(P(0, 1));

    for(int i = 1; i < k; ++i){

        int foo = i * 10 % k;

        if(foo == i)    continue;

        graph[i].push_back(P(foo, 0));

    }

    dist[1] = 1;

    deque<int> deq;

    deq.push_back(1);

    while(!deq.empty()){

        int from = deq.front();

        deq.pop_front();

        for(auto p : graph[from]){

            int to = p.first, cost = p.second;

            if(cost){

                if(dist[to] > dist[from] + cost){

                    dist[to] = dist[from] + cost;

                    deq.push_front(to);

                }

            }

            else{

                if(dist[to] > dist[from]){

                    dist[to] = dist[from];

                    deq.push_back(to);

                }

            }

        }

    }

    cout << dist[0] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



using ll = long long;

using ull = uint64_t;

using P = pair<int, int>;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



template<class T>

inline bool chmax(T& x, T y){

    if(x < y){

        x = y;

        return true;

    }

    return false;

}

template<class T>

inline bool chmin(T& x, T y){

    if(x > y){

        x = y;

        return true;

    }

    return false;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int K;

    cin >> K;

    vector<vector<P>> graph(K);

    for(int i = 0; i + 1 < K; ++i){

        graph[i].emplace_back(i + 1, 1);

        int v = i * 10 % K;

        graph[i].emplace_back(v, 0);

    }

    graph[K - 1].emplace_back(0, 1);

    graph[K - 1].emplace_back((K - 1) * 10 % K, 0);

    vector<int> dist(K, INF);

    dist[1] = 1;

    deque<int> deq;

    deq.push_back(1);

    while(!deq.empty()){

        int from = deq.front();

        deq.pop_front();

        for(auto e : graph[from]){

            int to = e.first, cost = e.second;

            if(!cost){

                if(chmin(dist[to], dist[from])) deq.push_front(to);

            }

            else{

                if(chmin(dist[to], dist[from] + 1)) deq.push_back(to);

            }

        }

    }

    cout << dist[0] << endl;

}

// Fastest known solution for this problem: