Untitled

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;

void test_case() {
    int k;
    cin >> k;
    unordered_set<int> s1;
    int g = 1;
    while (true) {
        if (s1.contains(g)) {
            break;
        } else {
            s1.insert(g);
            g = g * 10 % k;
        }
    }
    vector<int> s = {s1.begin(), s1.end()};
    vector<int> d(k, 50);
    priority_queue<pair<int, int>> q;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [cost, rem] = q.top();
        q.pop();
        cost *= -1;
        if (cost > d[rem]) continue;
        for (int ost : s) {
            int v = (ost + rem) % k;
            if (d[v] > cost + 1) {
                d[v] = cost + 1;
                q.emplace(-d[v], v);
                if (v == 0) {
                    break;
                }
            }
        }
    }
    cout << d[0];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}